結果
問題 | No.2930 Larger Mex |
ユーザー |
![]() |
提出日時 | 2024-10-12 15:51:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 118 ms / 2,000 ms |
コード長 | 2,099 bytes |
コンパイル時間 | 1,005 ms |
コンパイル使用メモリ | 77,192 KB |
最終ジャッジ日時 | 2025-02-24 18:14:05 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
#include <iostream> #include <vector> using namespace std; typedef long long ll; ll INF = 1000000000000000000; struct segment_tree{ int n; vector<ll> seg; ll e(){return INF;} ll op(ll a,ll b){return min(a,b);} segment_tree(){} segment_tree(int sz){n = sz; seg.resize(2*n,e());} segment_tree(vector<ll> v){ n = v.size(); seg.resize(2*n,e()); for(int i=0;i<n;i++) seg[i + n] = v[i]; for(int i=n - 1;i>0;i--) seg[i] = op(seg[i<<1],seg[i<<1|1]); } void init(int sz){n = sz; seg.resize(2*n);} void update(int p,ll val){ for(seg[p += n] = val;p>1;p>>=1) seg[p>>1] = op(seg[p],seg[p^1]); } ll get(int p){return seg[p + n];} ll query(int l,int r){ ll res = e(); for(l += n,r += n; l<r;l>>=1,r>>=1){ if(l&1) res = op(res,seg[l++]); if(r&1) res = op(res,seg[--r]); } return res; } int bin(int l,ll x){//seg.query(l,r - 1)<x,seg,qeury(l,r)>=x, return r; int le = l,ri = n; while(ri - le>1){ int mid = (le + ri)/2; if(query(l,mid)>=x) ri = mid; else le = mid; } return ri; } void clear(){for(int i=0;i<2*n;i++) seg[i] = e();} }; int a[200010]; int main(){ int i,n,m; cin >> n >> m; for(i=0;i<n;i++) cin >> a[i]; vector<ll> v(m),ans(n + 2); segment_tree seg(v); ll ri = 0; for(i=0;i<n;i++){ // [i,ri)がok ri = max(ri,(ll)i); while(ri<n && seg.query(0,m)==0){ if(a[ri]<m){ seg.update(a[ri],seg.get(a[ri]) + 1); } ri++; } // if(seg.query(0,m)>=1){ // cout << "[" << i << "," << ri << ")" << "\n"; // }else{ // cout << "[" << i << "," << -1 << ")" << "\n"; // } if(seg.query(0,m)>=1){ ans[ri - i]++; ans[n + 1 - i]--; } if(a[i]<m){ seg.update(a[i],seg.get(a[i]) - 1); } } for(i=1;i<=n;i++) ans[i] += ans[i - 1]; for(i=1;i<=n;i++) cout << ans[i] << "\n"; }