Submission #632907

#TimeUsernameProblemLanguageResultExecution timeMemory
632907berrZamjene (COCI16_zamjene)C++17
84 / 140
3867 ms138488 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N=1e6+37; int par[N], val[N], ind[N], pairs, poww[N], a[N], s[N], countt[N]; int hashh=1e6+37, mod=1e9+7, q, n; map<int, int> diff; void add(int a, int b, int x) { if(b!=0) { pairs+=a*x*diff[-b]; } diff[b]+=a*x; } int find(int x) { return par[x]=((par[x]==x)?x:(find(par[x]))); } void add2(int sgn, int p, int pos, int x) { ind[p]+= sgn*poww[pos]; val[p]+=sgn*poww[x]; countt[p]+=sgn; } void dsu(int x, int y) { x=find(x); y=find(y); if(x==y) return; add(-1, ind[x]-val[x], countt[x]); add(-1, ind[y]-val[y], countt[y]); par[y]=x; ind[x]+=ind[y]; val[x]+=val[y]; countt[x]+=countt[y]; add(1, ind[x]-val[x], countt[x]); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>q; for(int i=0; i<n; i++) { cin>>a[i]; s[i]=a[i]; par[i]=i; countt[i]=1; } poww[0]=1; for(int i=1 ; i<N; i++) { poww[i]=(poww[i-1]*hashh)%mod; } sort(s, s+n); for(int i=0; i<n; i++) { ind[i]=poww[s[i]]; val[i]=poww[a[i]]; add(1, ind[i] - val[i], countt[i]); } while(q--) { int type; cin>>type; if(type==1) { int x, y; cin>>x>>y; x--; y--; int px=find(x), py=find(y); if(px==py) { swap(a[x], a[y]); continue; } add(-1, ind[px]-val[px], countt[px]); add(-1, ind[py]-val[py], countt[py]); add2(-1, px, x, a[x]); add2(-1, py, y, a[y]); swap(a[x], a[y]); add2(1, px, x, a[x]); add2(1, py, y, a[y]); add(1, ind[px]-val[px], countt[px]); add(1, ind[py]-val[py], countt[py]); } if(type==2) { int x, y; cin>>x>>y; x--; y--; dsu(x, y); } if(type==3) { if(diff[0]==n) cout<<"DA\n"; else cout<<"NE\n"; } if(type==4) { cout<<pairs<<"\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...