AOJ 1148: Analyzing Login/Logout Records
問題
Analyzing Login/Logout Records | Aizu Online Judge
- パソコンのログイン/ログアウト履歴が与えられる
- 学生mがts〜teの間に1台以上のPCを利用していた時間を答えよ
方針
- 学生ごとにPC nのログイン・ログアウトの時間を記録する
- いもす法の気持ちで1台以上のPCを使っている時間帯の開始と終了を求めて足していく
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for(int i=0; i<(n); ++i) class history { public: int pc, start, end; history(int p, int s, int e) { pc = p; start = s; end = e; } }; int main(void){ vector<history> hist[10010]; int N, M; int r, t, n, m, s, q, ts, te; int imos[1265]; while(cin >> N >> M && N) { rep(i, 10010) hist[i].clear(); cin >> r; rep(i, r) { cin >> t >> n >> m >> s; if(s==1) { hist[m].push_back(history(n, t, -1)); } else { rep(j, hist[m].size()) { if(hist[m][j].pc == n && hist[m][j].end == -1) { hist[m][j].end = t; break; } } } } cin >> q; rep(i, q) { cin >> ts >> te >> m; rep(j, 1265) imos[j] = 0; rep(j, hist[m].size()) { if(hist[m][j].start < te && hist[m][j].end > ts) { imos[max(hist[m][j].start, ts)] += 1; imos[min(hist[m][j].end, te)] -= 1; } } int ans = 0; int cnt = 0; int start; rep(j, 1265) { if(cnt == 0 && imos[j] > 0) { start = j; } if(cnt > 0 && cnt+imos[j] == 0) { ans += (j - start); } cnt += imos[j]; } cout << ans << endl; } } }
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1895189
反省
- 使用時間帯をうまく求められなくて無限に時間がかかった
- クラスを用意するなんて大げさなことをしなくても解けたっぽい