日々精進

aikoと旅行とプログラミング

【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;
    }
  }
}