/*input
8
0
0
0
8
7
0
6
5
0
0
4
3
0
2
1
*/
#include<bits/stdc++.h>
using namespace std;
const int N=2e5 + 100;
const int mod=1e9 + 7;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second
#define mp make_pair
vector<int> adjlist[2*N];int arr[2*N], n;
int pos[2*N], ans[2*N];//vals[pos[i]] gives the set of values for the ith node.
int cval, nxt;
int tree[4*N];int ssum[2*N];
vector<int> vals[2*N];
void build(int i=1, int l=1, int r=n)
{
tree[i]=0;
if(l==r) return;
int mid=(l+r)>>1;build(2*i, l, mid);build(2*i+1, mid+1, r);
}
int curpos;
void remove(int i=1, int l=1, int r=n)
{
if(tree[i]==0) return;
if(l==r)
{
vals[curpos].push_back(l);tree[i]=0;return;
}
tree[i]=0;int mid=(l+r)>>1;remove(2*i, l, mid);remove(2*i+1, mid+1, r);
}
int ql, qr;
void update(int i=1, int l=1, int r=n)
{
if(l>qr||r<ql) return;
if(l>=ql&&r<=qr)
{
tree[i]=1;return;
}
int mid=(l+r)>>1;update(2*i, l, mid);update(2*i+1, mid+1, r);
tree[i]=tree[2*i] + tree[2*i+1];
}
int query(int i=1, int l=1, int r=n)
{
if(l>qr||r<ql) return 0;
if(l>=ql&&r<=qr) return tree[i];
int mid=(l+r)>>1;return query(2*i, l, mid) + query(2*i+1, mid+1, r);
}
void dfs(int i)
{
int v;cin>>v;
if(v==0)
{
adjlist[i].push_back(cval);
dfs(cval++);
adjlist[i].push_back(cval);dfs(cval++);ssum[i]=ssum[adjlist[i][1]]+ssum[adjlist[i][0]];
if(ssum[adjlist[i][0]]>ssum[adjlist[i][1]]) swap(adjlist[i][0], adjlist[i][1]);
}
else
{
arr[i]=v;ssum[i]=1;
pos[i]=nxt++;
return;
}
}
void mdfs(int i)
{
if(adjlist[i].empty())
{
ans[i]=0;ql=qr=arr[i];update();
return;
}
mdfs(adjlist[i][0]);curpos=adjlist[i][0];
remove();
mdfs(adjlist[i][1]);ql=1;qr=n;
int prevsum=query();int tot=0, prevpos=n;
reverse(vals[curpos].begin(), vals[curpos].end());
for(auto j:vals[curpos])
{
ql=1;qr=j-1;tot+=query();
}
if(i==2)
{
cout<<curpos<<": ";
for(auto j:vals[curpos]) cout<<j<<" ";cout<<endl<<endl;
}
for(auto j:vals[curpos])
{
ql=qr=j;update();
}
if(i==2)
{
cout<<tree[1]<<endl;
}
ans[i]=ans[adjlist[i][0]] + ans[adjlist[i][1]] + min(tot, ssum[adjlist[i][0]]*ssum[adjlist[i][1]] - tot);
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
cin>>n;cval=2;nxt=1;
dfs(1);
mdfs(1);
/* for(int i=1;i<=15;i++) {cout<<i<<": ";//<<ans[i]<<endl;
for(auto j:vals[i]) cout<<j<<" ";cout<<endl;
// cout<<" val="<<arr[i]<<endl;
}*/
cout<<ans[1];
}
Compilation message
rot.cpp: In function 'void mdfs(long long int)':
rot.cpp:105:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(auto j:vals[curpos]) cout<<j<<" ";cout<<endl<<endl;
^~~
rot.cpp:105:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(auto j:vals[curpos]) cout<<j<<" ";cout<<endl<<endl;
^~~~
rot.cpp:95:6: warning: unused variable 'prevsum' [-Wunused-variable]
int prevsum=query();int tot=0, prevpos=n;
^~~~~~~
rot.cpp:95:33: warning: unused variable 'prevpos' [-Wunused-variable]
int prevsum=query();int tot=0, prevpos=n;
^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
19192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
19328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
19840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
30 ms |
21376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
26872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
35512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
182 ms |
36880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
303 ms |
47260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
307 ms |
48228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
327 ms |
49284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
