結果
問題 | No.2687 所により大雨 |
ユーザー |
|
提出日時 | 2024-03-20 21:52:34 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 106 ms / 2,000 ms |
コード長 | 1,095 bytes |
コンパイル時間 | 649 ms |
コンパイル使用メモリ | 72,136 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-09-30 07:40:22 |
合計ジャッジ時間 | 2,984 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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,r-1,r+1})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"); } }