Submission #1020397

#TimeUsernameProblemLanguageResultExecution timeMemory
1020397KhoaDuyUntitled (POI11_rot)C++14
0 / 100
904 ms65536 KiB
#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); 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:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i<leaf[right].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...