結果
問題 | No.1675 Strange Minimum Query |
ユーザー |
|
提出日時 | 2021-09-10 21:30:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 321 ms / 2,000 ms |
コード長 | 773 bytes |
コンパイル時間 | 832 ms |
コンパイル使用メモリ | 86,324 KB |
実行使用メモリ | 20,168 KB |
最終ジャッジ日時 | 2024-06-11 22:34:00 |
合計ジャッジ時間 | 10,860 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
コンパイルメッセージ
main.cpp:11:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 11 | main() | ^~~~
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<queue> #include<atcoder/segtree> using namespace std; int op(int a,int b){return a<b?a:b;} int e(){return 2e9;} int N,Q; vector<pair<int,int> >L[2<<17]; main() { cin>>N>>Q; for(int i=0;i<Q;i++) { int l,r,b;cin>>l>>r>>b; L[l-1].push_back(make_pair(b,r)); } priority_queue<pair<int,int> >P; vector<int>A(N); P.push(make_pair(1,N)); for(int l=0;l<N;l++) { while(P.top().second<=l)P.pop(); for(pair<int,int>p:L[l])P.push(p); A[l]=P.top().first; } atcoder::segtree<int,op,e>Q(A); for(int l=0;l<N;l++) { for(pair<int,int>p:L[l]) { int r=p.second,b=p.first; if(Q.prod(l,r)!=b) { cout<<-1<<endl; return 0; } } } for(int i=0;i<N;i++)cout<<A[i]<<(i+1==N?"\n":" "); }