Submission #1116247

#TimeUsernameProblemLanguageResultExecution timeMemory
1116247FubuGoldUntitled (POI11_rot)C++14
0 / 100
1060 ms40776 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 500000; struct BIT { vector<int> tree; int n; void init(int _n) { n = _n; tree.assign(n+1,0); } void update(int pos,int val) { for (;pos <= n;pos += pos & -pos) tree[pos] += val; } int query(int pos) { int sum = 0; for (;pos > 0;pos -= pos & -pos) sum += tree[pos]; return sum; } int query(int l,int r) { if (l > r) return 0; return query(r) - query(l-1); } } tree; vector<int> adj[MAXN+1]; stack<pair<int,int>> st; vector<int> ch[MAXN+1]; int val[MAXN+1]; int sz[MAXN+1]; int n,m; int cnt; long long ans = 0; int cal_sz(int u) { if (adj[u].size() == 0) return sz[u] = 1; sz[u] += cal_sz(adj[u][0]); sz[u] += cal_sz(adj[u][1]); return sz[u]; } void dfs(int u,int keep) { if (adj[u].size() == 0) { ch[u].push_back(val[u]); if (keep) tree.update(val[u],1); return; } int lt = adj[u][0], rt = adj[u][1]; long long tmp = 0; if (sz[lt] < sz[rt]) { dfs(lt,0); dfs(rt,1); ch[u].swap(ch[rt]); for (int i=0;i<ch[lt].size();i++) { int v = ch[lt][i]; ch[u].push_back(v); // cerr << u << ' ' << v << '\n'; tmp += tree.query(1,v-1); } for (int i=0;i<ch[lt].size();i++) { tree.update(ch[lt][i],1); } } else { dfs(rt,0); dfs(lt,1); ch[u].swap(ch[lt]); for (int i=0;i<ch[rt].size();i++) { int v = ch[rt][i]; // cerr << u << ' ' << v << '\n'; ch[u].push_back(v); tmp += tree.query(v+1,m); } for (int i=0;i<ch[rt].size();i++) { tree.update(ch[rt][i],1); } } tmp = min(tmp,1ll * sz[lt] * sz[rt] - tmp); // cerr << u << ' ' << tmp << '\n'; // cerr << tree.query(1,m) << '\n'; ans += tmp; if (!keep) { for (int i=0;i<ch[u].size();i++) { tree.update(ch[u][i],-1); } } } int main() { cin.tie(0) -> sync_with_stdio(0); cin >> m; tree.init(m); for (n=1;;n++) { cin >> val[n]; if (st.size()) adj[st.top().first].push_back(n); if (val[n] != 0) cnt++; if (val[n] != 0 && st.top().second == 2) st.pop(); else if (val[n] != 0) st.top().second++; else { st.push({n,1}); } if (cnt == m) break; } cal_sz(1); dfs(1,1); cout << ans; return 0; }

Compilation message (stderr)

rot.cpp: In function 'void dfs(int, int)':
rot.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int i=0;i<ch[lt].size();i++) {
      |                      ~^~~~~~~~~~~~~~
rot.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for (int i=0;i<ch[lt].size();i++) {
      |                      ~^~~~~~~~~~~~~~
rot.cpp:70:23: 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<ch[rt].size();i++) {
      |                      ~^~~~~~~~~~~~~~
rot.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int i=0;i<ch[rt].size();i++) {
      |                      ~^~~~~~~~~~~~~~
rot.cpp:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for (int i=0;i<ch[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...