読者です 読者をやめる 読者になる 読者になる

UVa11926 Multitasking

解法
計算量が3*10^9くらいになるので嘘解法かもしれないが、いもす法で解いた。

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX (1000000)
 
int main() {
   
  int N, M;
  while(cin >> N >> M && (N|M)) {
    int arr[MAX+1] = {};
    for(int i=0; i<N; i++) {
      int s, t; cin >> s >> t;
      arr[s] ++;
      arr[t] --;
    }
     
    for(int i=0; i<M; i++) {
      int s, t; cin >> s >> t;
      int interval; cin >> interval;
       
      int now = s;
      int diff = t-s;
      while(now <= MAX) {
        arr[now] ++;
        if(now+diff > MAX) break;
        arr[now+diff] --;
        now += interval;
      }
    }
     
    int sum[MAX+2];
    sum[0] = 0;
     
    for(int i=0; i<=MAX; i++) {
      sum[i+1] = sum[i] + arr[i];
    }
     
    bool ok = true;
    for(int i=0; i<=MAX+1; i++) {
      if(sum[i] >= 2) {
        ok = false;
        break;
      }
    }
     
    if(ok) {
      cout << "NO CONFLICT" << endl;
    }
    else {
      cout << "CONFLICT" << endl;
    }
  }
   
  return 0;
}