結果
問題 | No.833 かっこいい電車 |
ユーザー | beet |
提出日時 | 2019-05-24 21:44:51 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 139 ms / 2,000 ms |
コード長 | 4,202 bytes |
コンパイル時間 | 2,663 ms |
コンパイル使用メモリ | 235,728 KB |
実行使用メモリ | 31,020 KB |
最終ジャッジ日時 | 2023-09-14 20:50:31 |
合計ジャッジ時間 | 6,363 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 139 ms
31,020 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 109 ms
19,736 KB |
testcase_11 | AC | 139 ms
23,112 KB |
testcase_12 | AC | 42 ms
8,932 KB |
testcase_13 | AC | 32 ms
7,992 KB |
testcase_14 | AC | 106 ms
17,296 KB |
testcase_15 | AC | 52 ms
10,332 KB |
testcase_16 | AC | 37 ms
8,396 KB |
testcase_17 | AC | 43 ms
9,752 KB |
testcase_18 | AC | 133 ms
22,024 KB |
testcase_19 | AC | 38 ms
8,124 KB |
testcase_20 | AC | 11 ms
4,376 KB |
testcase_21 | AC | 117 ms
19,636 KB |
testcase_22 | AC | 65 ms
12,132 KB |
testcase_23 | AC | 44 ms
9,632 KB |
testcase_24 | AC | 65 ms
12,024 KB |
testcase_25 | AC | 129 ms
21,600 KB |
testcase_26 | AC | 46 ms
9,004 KB |
testcase_27 | AC | 87 ms
14,748 KB |
testcase_28 | AC | 67 ms
12,980 KB |
testcase_29 | AC | 76 ms
13,824 KB |
testcase_30 | AC | 78 ms
19,700 KB |
testcase_31 | AC | 134 ms
31,000 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} struct PersistentUnionFind{ using T = tuple<Int, Int, Int, Int>; Int n; vector<Int> r,p,L,R; stack<T> st; PersistentUnionFind(){} PersistentUnionFind(Int sz):n(sz),r(sz,1),p(sz,0){ iota(p.begin(),p.end(),0); L=R=p; } Int find(Int x){ return x==p[x]?p[x]:find(p[x]); } bool same(Int x,Int y){ return find(x)==find(y); } void unite(Int x,Int y){ x=find(x);y=find(y); st.emplace(-1,-1,-1,-1); if(x==y) return; if(r[x]<r[y]) swap(x,y); st.top()=T(x,y,L[x],R[x]); // cout<<x<<":"<<L[x]<<" "<<R[x]<<endl; r[x]+=r[y]; p[y]=x; L[x]=min(L[x],L[y]); R[x]=max(R[x],R[y]); } void undo(Int t=1){ for(Int i=0;i<t;i++){ Int x,y,ll,rr; tie(x,y,ll,rr)=st.top();st.pop(); if(x<0) continue; r[x]-=r[y]; p[y]=y; L[x]=ll; R[x]=rr; //cout<<x<<";"<<L[x]<<" "<<R[x]<<endl; } } Int getL(Int x){return L[find(x)];}; Int getR(Int x){return R[find(x)];}; }; struct DynamicConnectivity{ using edge = pair<Int, Int>; using range = edge; Int n,q; PersistentUnionFind puf; vector<vector<edge> > edges; vector<pair<range, edge> > prc; map<edge, Int> cnt,app; DynamicConnectivity(){} DynamicConnectivity(Int n,Int q_):n(n),q(1),puf(n){ while(q<q_) q<<=1; edges.resize(q*2-1); } void insert(Int t,Int u,Int v){ edge e=minmax({u,v}); if(cnt[e]++==0) app[e]=t; } void erase(Int t,Int u,Int v){ edge e=minmax({u,v}); if(--cnt[e]==0) prc.emplace_back(range(app[e],t),e); } void add(Int a,Int b,const edge &e,Int k,Int l,Int r){ if(r<=a||b<=l) return; if(a<=l&&r<=b){ edges[k].emplace_back(e); return; } Int m=(l+r)>>1; add(a,b,e,k*2+1,l,m); add(a,b,e,k*2+2,m,r); } void add(range &r,const edge &e){ add(r.first,r.second,e,0,0,q); } void build(){ for(auto &e:cnt){ if(!e.second) continue; prc.emplace_back(range(app[e.first],q),e.first); } for(auto &s:prc) add(s.first,s.second); } void exec(function<void(Int)> &f,Int k=0){ for(auto &e:edges[k]) puf.unite(e.first,e.second); if(k<q-1){ exec(f,k*2+1); exec(f,k*2+2); }else{ Int x=k-(q-1); f(x); } puf.undo(edges[k].size()); } }; template<typename T> struct BIT{ Int n; vector<T> bit; //1-indexed BIT():n(-1){} BIT(Int n_,T d):n(n_),bit(n_+1,d){} T sum(Int i){ T s=bit[0]; for(Int x=i;x>0;x-=(x&-x)) s+=bit[x]; return s; } void add(Int i,T a){ if(i==0) return; for(Int x=i;x<=n;x+=(x&-x)) bit[x]+=a; } Int lower_bound(Int w){ if(w<=0) return 0; Int x=0,r=1; while(r<n) r<<=1; for(Int k=r;k>0;k>>=1){ if(x+k<=n&&bit[x+k]<w){ w-=bit[x+k]; x+=k; } } return x+1; } T sum0(Int i){ return sum(i+1); } void add0(Int i,T a){ add(i+1,a); } T query(Int l,Int r){ return sum(r-1)-sum(l-1); } T query0(Int l,Int r){ return sum(r)-sum(l); } }; //INSERT ABOVE HERE signed main(){ Int n,q; cin>>n>>q; vector<Int> a(n); for(Int i=0;i<n;i++) cin>>a[i]; vector<Int> t(q),x(q); for(Int i=0;i<q;i++) cin>>t[i]>>x[i],x[i]--; vector<Int> con(n,0); DynamicConnectivity G(n,q); for(Int i=0;i<q;i++){ if(t[i]==1){ if(con[x[i]]==1) continue; con[x[i]]=1; G.insert(i,x[i],x[i]+1); } if(t[i]==2){ if(con[x[i]]==0) continue; con[x[i]]=0; G.erase(i,x[i],x[i]+1); } } G.build(); BIT<Int> bit(n+1,0); for(Int i=0;i<n;i++) bit.add0(i,a[i]); function<void(Int)> f= [&](Int i){ if(i>=q||t[i]==1||t[i]==2) return; if(t[i]==3){ bit.add0(x[i],1); return; } assert(t[i]==4); Int L=G.puf.getL(x[i]); Int R=G.puf.getR(x[i]); //cout<<L<<" "<<R<<endl; cout<<bit.query0(L,R+1)<<"\n"; }; G.exec(f); cout<<flush; return 0; }