Submission #532473

#TimeUsernameProblemLanguageResultExecution timeMemory
532473colazcyZamjene (COCI16_zamjene)C++17
140 / 140
4178 ms180628 KiB
#include <cstdio> #include <cassert> #include <vector> #include <random> #include <chrono> #include <set> #include <map> #include <algorithm> #define let const auto #define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++) #define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--) #define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++) #define debug(...) fprintf(stderr,__VA_ARGS__) #define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__) using ll = long long; using ull = unsigned long long; constexpr int maxn = 1e6 + 10; ull trans[maxn]; int n,q,now[maxn],target[maxn]; std::mt19937_64 eng(743); namespace dsu{ int f[maxn],sz[maxn]; void init(){ rep(i,1,n)f[i] = i,sz[i] = 1; } int find(const int x){return x == f[x] ? x : f[x] = find(f[x]);} }; std::map<ull,int> mp; ll ans; ull sum[maxn]; void ins(const ull s,const int sz){ if(s != 0)ans += 1ll * sz * mp[-s]; mp[s] += sz; } void del(const ull s,const int sz){ mp[s] -= sz; if(s != 0)ans -= 1ll * sz * mp[-s]; } void init(){ rep(i,1,n)target[i] = now[i]; std::sort(target + 1,target + 1 + n); rep(i,1,n)trans[now[i]] = eng(); dsu::init(); rep(i,1,n) sum[i] = trans[now[i]] - trans[target[i]]; rep(i,1,n)ins(sum[i],1); } void modify_swap(const int a,const int b){ let x = dsu::find(a),y = dsu::find(b); if(x == y){ std::swap(now[a],now[b]); return; } del(sum[x],dsu::sz[x]); del(sum[y],dsu::sz[y]); sum[x] -= trans[now[a]]; sum[y] -= trans[now[b]]; std::swap(now[a],now[b]); sum[x] += trans[now[a]]; sum[y] += trans[now[b]]; ins(sum[x],dsu::sz[x]); ins(sum[y],dsu::sz[y]); } void modify_merge(const int a,const int b){ let x = dsu::find(a),y = dsu::find(b); if(x == y)return; del(sum[x],dsu::sz[x]); del(sum[y],dsu::sz[y]); sum[y] += sum[x]; dsu::sz[y] += dsu::sz[x]; dsu::f[x] = y; ins(sum[y],dsu::sz[y]); } bool query_sort(){ return mp[0] == n; } ll query_count(){ return ans; } int main(){ // std::freopen("zamjene.in","r",stdin); // std::freopen("zamjene.out","w",stdout); std::scanf("%d %d",&n,&q); rep(i,1,n)std::scanf("%d",now + i); init(); repn(q){ int opt,x,y; std::scanf("%d",&opt); if(opt == 1){ std::scanf("%d %d",&x,&y); modify_swap(x,y); }else if(opt == 2){ std::scanf("%d %d",&x,&y); modify_merge(x,y); }else if(opt == 3)std::puts(query_sort() ? "DA" : "NE"); else if(opt == 4)std::printf("%lld\n",query_count()); } std::fclose(stdin); std::fclose(stdout); return 0; }

Compilation message (stderr)

zamjene.cpp: In function 'int main()':
zamjene.cpp:85:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |  std::scanf("%d %d",&n,&q);
      |  ~~~~~~~~~~^~~~~~~~~~~~~~~
zamjene.cpp:86:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  rep(i,1,n)std::scanf("%d",now + i);
      |            ~~~~~~~~~~^~~~~~~~~~~~~~
zamjene.cpp:89:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   int opt,x,y; std::scanf("%d",&opt);
      |                ~~~~~~~~~~^~~~~~~~~~~
zamjene.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |    std::scanf("%d %d",&x,&y);
      |    ~~~~~~~~~~^~~~~~~~~~~~~~~
zamjene.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |    std::scanf("%d %d",&x,&y);
      |    ~~~~~~~~~~^~~~~~~~~~~~~~~
#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...