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