Submission #1020506

#TimeUsernameProblemLanguageResultExecution timeMemory
1020506KhoaDuyUntitled (POI11_rot)C++17
36 / 100
1050 ms65536 KiB
// Judges with GCC >= 12 only needs Ofast #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize") // MLE optimization #pragma GCC optimize("conserve-stack") // Old judges #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2") // New judges. Test with assert(__builtin_cpu_supports("avx2")); // #pragma GCC target("arch=skylake") // Atcoder // #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma") #include<bits/stdc++.h> using namespace std; #define endl '\n' const int MAXN=4*1e5; vector<vector<int>> graph(MAXN+1); vector<vector<int>> leaf; int seg[MAXN]={0}; int n; int ptr=0; long long ans=0; void build(int l,int r){ l+=n,r+=n; while(l>1){ l>>=1,r>>=1; for(int v=l;v<=r;v++){ seg[v]=seg[v<<1]+seg[(v<<1)|1]; } } } void modify(int i,int x){ i+=n; seg[i]+=x; build(i-n,i-n); } long long query(int l,int r){ if(l>r){ return 0; } l+=n,r+=n; int curr=0; for(;l<=r;l>>=1,r>>=1){ if(l&1){ curr+=seg[l]; l++; } if(!(r&1)){ curr+=seg[r]; r--; } } return curr; } void DFS(int u,bool keep){ if(!graph[u].size()){ leaf[u].push_back(u); if(keep){ modify(u-1,1); } return; } int left=graph[u][0],right=graph[u][1]; if(leaf[left].size()<leaf[right].size()){ swap(left,right); } DFS(right,false); DFS(left,true); swap(leaf[u],leaf[left]); long long tot=leaf[u].size()*leaf[right].size(); long long inver=0; for(int i=0;i<leaf[right].size();i++){ inver+=query(leaf[right][i],n-1); } ans+=min(inver,tot-inver); if(!keep){ for(int i=0;i<leaf[u].size();i++){ modify(leaf[u][i]-1,-1); } } leaf[u].reserve(leaf[u].size()+leaf[right].size()); while(!leaf[right].empty()){ leaf[u].push_back(leaf[right].back()); if(keep){ modify(leaf[right].back()-1,1); } leaf[right].pop_back(); } } vector<int> input; int tim; int Buildtree(){ if(input[ptr]!=0){ ptr++; return input[ptr-1]; } ptr++; int u=tim; tim++; int v=Buildtree(); graph[u].push_back(v); v=Buildtree(); graph[u].push_back(v); return u; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; tim=n+1; cin.ignore(); string line; while(getline(cin,line)){ if(line.empty()){ break; } stringstream ss; ss << line; int x=0; ss >> x; input.push_back(x); } int root=Buildtree(); leaf.resize(tim); DFS(root,true); cout << ans; }

Compilation message (stderr)

rot.cpp: In function 'void DFS(int, bool)':
rot.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0;i<leaf[right].size();i++){
      |                 ~^~~~~~~~~~~~~~~~~~~
rot.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int i=0;i<leaf[u].size();i++){
      |                     ~^~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...