【AOJ 1148】Analyzing Login/Logout Records
問題
Analyzing Login/Logout Records | Aizu Online Judge
方針
- PCの番号nと生徒の番号mをキーとしたmapを使って計算する.
- ログには必ずログインとログアウトの記録が存在し, 時刻昇順で入力がされることからk番目をstart, k+1番目をend(ただしkは偶数)としてPC使用時間をboolの配列で管理した.
- 最後にしゃくとりで答えを求める.
ソース
#include <iostream> #include <utility> #include <map> #include <vector> using namespace std; #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) #define pb push_back typedef pair<int, int> P; signed main(){ int N,M; int r, q; cin.tie(0); ios::sync_with_stdio(false); while(cin >> N >> M, N || M){ cin >> r; int t, n, m, s; map<P, vector<P> > data; rep(i, r){ cin >> t >> n >> m >> s; data[P(n,m)].pb(P(t, s)); } cin >> q; rep(i, q){ int ts, te, qm; cin >> ts >> te >> qm; bool flag[1261]; fill(flag, flag+1260, false); REP(j, 1, N+1){ for(int k = 0 ; k < (int)data[P(j, qm)].size() ; k+=2){ int start = max(data[P(j, qm)][k].first, ts); int end = min(data[P(j, qm)][k+1].first, te); REP(l, start, end+1){ flag[l] = true; } } } int ans = 0; REP(j, ts, te){ if(flag[j]){ int start = j; while(flag[j]) j++; ans+=(j-start-1); } } cout << ans << endl; } } }