結果
問題 | No.2687 所により大雨 |
ユーザー |
|
提出日時 | 2024-03-21 01:22:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 106 ms / 2,000 ms |
コード長 | 1,086 bytes |
コンパイル時間 | 751 ms |
コンパイル使用メモリ | 71,040 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-09-30 09:54:50 |
合計ジャッジ時間 | 3,239 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 25 |
ソースコード
#include<iostream> #include<algorithm> #include<cassert> using namespace std; int N,M; pair<int,int>LR[1<<17]; pair<int,int>nLR[1000]; int K; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N>>M; for(int i=0;i<N;i++)cin>>LR[i].first>>LR[i].second; for(int i=0;i<M;i++)cin>>nLR[i].first>>nLR[i].second; cin>>K; sort(LR,LR+N); sort(nLR,nLR+M); { bool fn=false; for(int i=0;i+1<N;i++)if(LR[i].second>=LR[i+1].first)fn=true; for(int i=0;i+1<M;i++)if(nLR[i].second>=nLR[i+1].first)fn=true; if(fn) { for(;K--;) { int P;cin>>P; cout<<1<<(K?" ":"\n"); } return 0; } } for(;K--;) { int P;cin>>P; bool fn=false; for(int i=0;i<M;i++) { long tL=nLR[i].first-P,tR=nLR[i].second-P; int l=-1,r=N; while(r-l>1) { int mid=(l+r)/2; if(P<=LR[mid].second+tR)r=mid; else l=mid; } for(int j:{r})if(j>=0&&j<N) { long ntL=max(tL,(long)P-LR[j].second); long ntR=min(tR,(long)P-LR[j].first); if(ntL<=ntR) { fn=true; break; } } if(fn)break; } cout<<fn<<(K?" ":"\n"); } }