Submission #132350

#TimeUsernameProblemLanguageResultExecution timeMemory
132350nikolapesic2802Zamjene (COCI16_zamjene)C++14
0 / 140
1816 ms250668 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define ll long long #define pb push_back #define sz(x) (int)(x).size() #define mp make_pair #define f first #define s second #define all(x) x.begin(), x.end() #define D(x) cerr << #x << " is " << (x) << "\n"; using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key() template<class T1, class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; } template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;} template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;} gp_hash_table<int,int> cnt; const int mod=1e9+7,m=1e6+1,N=1e6+1; vector<int> par(N),pwr,p,q,hsh(N); vector<multiset<int> > imam(N),treba(N); int n,qq; ll ans4; int ans3; int mul(int a,int b) { return (ll)a*b%mod; } int add(int a,int b) { a+=b; if(a>=mod) a-=mod; return a; } int sub(int a,int b) { a-=b; if(a<0) a+=mod; return a; } int find(int tr) { if(par[tr]==tr) return tr; return par[tr]=find(par[tr]); } void merge(int a,int b) { a=find(a); b=find(b); if(a==b) return; if(hsh[a]!=0) ans4-=(ll)imam[a].size()*cnt[sub(0,hsh[a])],ans3--; if(hsh[b]!=0) ans4-=(ll)imam[b].size()*cnt[sub(0,hsh[b])],ans3--; cnt[hsh[a]]-=imam[a].size(); cnt[hsh[b]]-=imam[b].size(); if(imam[a].size()<imam[b].size()) swap(a,b); for(auto d:imam[b]) hsh[a]=add(hsh[a],pwr[d]),imam[a].insert(d); for(auto d:treba[b]) hsh[a]=sub(hsh[a],pwr[d]),treba[a].insert(d); imam[b].clear(); treba[b].clear(); par[b]=a; if(hsh[a]!=0) cnt[hsh[a]]+=imam[a].size(),ans4+=(ll)imam[a].size()*cnt[sub(0,hsh[a])],ans3++; } void swapuj(int a,int b) { int pa=p[a],pb=p[b]; swap(p[a],p[b]); a=find(a); b=find(b); if(a==b) return; if(hsh[a]!=0) ans4-=(ll)imam[a].size()*cnt[sub(0,hsh[a])],ans3--; if(hsh[b]!=0) ans4-=(ll)imam[b].size()*cnt[sub(0,hsh[b])],ans3--; cnt[hsh[a]]-=imam[a].size(); cnt[hsh[b]]-=imam[b].size(); hsh[a]=sub(hsh[a],pwr[pa]); hsh[a]=add(hsh[a],pwr[pb]); hsh[b]=sub(hsh[b],pwr[pb]); hsh[b]=add(hsh[b],pwr[pa]); imam[a].erase(imam[a].find(pa)); imam[a].insert(pb); imam[b].erase(imam[b].find(pb)); imam[b].insert(pa); cnt[hsh[a]]+=imam[a].size(); cnt[hsh[b]]+=imam[b].size(); if(hsh[a]!=0) ans4+=(ll)imam[a].size()*cnt[sub(0,hsh[a])],ans3++; if(hsh[b]!=0) ans4+=(ll)imam[b].size()*cnt[sub(0,hsh[b])],ans3++; } int main() { pwr.pb(1); for(int i=0;i<N;i++) par[i]=i,pwr.pb(mul(pwr.back(),m)); scanf("%i %i",&n,&qq); p.resize(n); for(int i=0;i<n;i++) scanf("%i",&p[i]); q=p; sort(all(q)); for(int i=0;i<n;i++) imam[i].insert(p[i]),hsh[i]=add(hsh[i],pwr[p[i]]),treba[i].insert(q[i]),hsh[i]=sub(hsh[i],pwr[q[i]]),cnt[hsh[i]]++; for(int i=0;i<n;i++) if(hsh[i]!=0) ans4+=cnt[sub(0,hsh[i])],ans3++; while(qq--) { int t,a,b; scanf("%i",&t); if(t==1) scanf("%i %i",&a,&b),swapuj(a-1,b-1); if(t==2) scanf("%i %i",&a,&b),merge(a-1,b-1); if(t==3) printf(ans3==0?"DA\n":"NE\n"); if(t==4) printf("%lld\n",ans4/2); } return 0; }

Compilation message (stderr)

zamjene.cpp: In function 'int main()':
zamjene.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i %i",&n,&qq);
     ~~~~~^~~~~~~~~~~~~~~~
zamjene.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&p[i]);
         ~~~~~^~~~~~~~~~~~
zamjene.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&t);
         ~~~~~^~~~~~~~~
zamjene.cpp:132:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i %i",&a,&b),swapuj(a-1,b-1);
             ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
zamjene.cpp:134:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%i %i",&a,&b),merge(a-1,b-1);
             ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
#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...