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

反省

• 使用時間帯をうまく求められなくて無限に時間がかかった
• クラスを用意するなんて大げさなことをしなくても解けたっぽい