PKU 3326 Analyzing Login/Logout Records

• やるだけ
• 時間の分だけ配列を取って塗りつぶしていく方法と、数直線状で扱う方法がある
• この解答は後者

int main() {
	for (int N, M; cin >> N >> M && (N || M); ) {
		int r;
		cin >> r;

		vector<vector<pair<int, int> > > loginout(M + 1);
		REP(i, r) {
			int t, n, m, s;
			cin >> t >> n >> m >> s;
			loginout[m].push_back(make_pair(t, 1 - s));
		}

		vector<vector<pair<int, int> > > data(M + 1);
		REP(m, M + 1) {
			sort(ALL(loginout[m]));
			int counter = 0;
			int start = INT_MAX;
			for (vector<pair<int, int> >::iterator it = loginout[m].begin(), itEnd = loginout[m].end(); it != itEnd; ++it) {
				if (it->second) {
					// logout
					if (--counter == 0) {
						data[m].push_back(make_pair(start, it->first));
					}

				} else {
					// login
					if (counter++ == 0) {
						start = it->first;
					}
				}
			}
		}

		int q;
		cin >> q;
		REP(i, q) {
			int ts, te, m;
			cin >> ts >> te >> m;

			int sum = 0;
			vector<pair<int, int> >& v = data[m];
			for (vector<pair<int, int> >::iterator it = v.begin(), itEnd = v.end(); it != itEnd; ++it) {
				const int begin = max(it->first, ts);
				const int end = min(it->second, te);
				if (begin < end) {
					sum += end - begin;
				}
			}
			cout << sum << endl;
		}
	}
}