結果
問題 | No.2930 Larger Mex |
ユーザー |
![]() |
提出日時 | 2024-10-12 16:03:28 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 370 ms / 2,000 ms |
コード長 | 2,433 bytes |
コンパイル時間 | 1,306 ms |
コンパイル使用メモリ | 84,636 KB |
最終ジャッジ日時 | 2025-02-24 18:22:46 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include<iostream> #include<vector> #include<queue> using namespace std; //遅延セグ木(自作) class seguki{ public: //1index vector<int>num; int siz=1; void init(int n){ while(siz<n)siz*=2; for (int i=0;i<siz*2+1;i++)num.emplace_back(0); } int access(int a){ a=siz+a-1; return num[a]; } //a,b半開区間 //mx_num(求めたい区間の半開区間(1~5だったら1,6),1,seguki.siz+1(セルのすべての半開区間),1(スタート地点のセル1)) int mx_num(int l,int r,int a,int b,int u){ if(r<=a || b<=l)return 0; else if(l<=a && b<=r)return num[u]; int m=(a+b)/2; int L=mx_num(l,r,a,m,u*2); int R=mx_num(l,r,m,b,u*2+1); return L+R; } void haiti(int l,int r,int a,int b,int u,int num2){ if(r<=a || b<=l)return ; else if(l<=a && b<=r){ num[u]+=num2; return ; } int m=(a+b)/2; haiti(l,r,a,m,u*2,num2); haiti(l,r,m,b,u*2+1,num2); } void orosu(int a){ if(a>=num.size())return; num[a*2]+=num[a]; num[a*2+1]+=num[a]; orosu(a*2); orosu(a*2+1); } }; int main() { int n,m; cin >> n >> m; if(m==0){ for(int i=0;i<n;i++)cout << n-i << endl; return 0; } vector<int>a(n); for(int i=0;i<n;i++)cin >> a[i]; vector<vector<int>>num(m+1); for(int i=0;i<n;i++)if(a[i]<m)num[a[i]].emplace_back(i+1); priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>prq; int must=0; for(int i=0;i<m;i++){ if(num[i].size()==0){ for(int i=0;i<n;i++)cout << 0 << endl; return 0; } prq.push(make_pair(num[i][0],i)); must=max(must,num[i][0]); } seguki ans; ans.init(n+1); bool ok=true; for(int t=1;t<=n;t++){ while(prq.top().first<t){ pair<int,int>hako=prq.top(); prq.pop(); int left=-1,right=num[hako.second].size(); while(left+1!=right){ int mokuteki=(left+right)/2; if(num[hako.second][mokuteki]<=hako.first)left=mokuteki; else right=mokuteki; } if(right==num[hako.second].size()){ ok=false; break; } prq.push(make_pair(num[hako.second][right],hako.second)); must=max(must,num[hako.second][right]); } if(ok==false)break; //ここまででどこまで取ればM未満が埋まるかが分かる。 ans.haiti(must-t+1,n-t+2,1,ans.siz+1,1,1); } ans.orosu(1); for(int i=0;i<n;i++)cout << ans.access(i+1) << endl; }