Submission #404143

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
404143	2021-05-13T22:01:47 Z	ScarletS	Tree Rotations (POI11_rot)	C++17	100 / 100	144 ms	17476 KB

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 2e5+7;
int bit[N],tin[N*2],tout[N*2],a[N],e[N*2][2],t,u;
ll ans;

int dfs()
{
    int x=u++,y;
    cin>>y;
    if (y==0)
    {
        e[x][0]=dfs();
        tin[x]=tin[e[x][0]];
        e[x][1]=dfs();
    }
    else
    {
        a[t]=y;
        tin[x]=t++;
    }
    tout[x]=t;
    return x;
}

void update(int i, int d)
{
    while (i<N)
    {
        bit[i]+=d;
        i+=i&-i;
    }
}

int query(int i)
{
    int r=0;
    while (i)
    {
        r+=bit[i];
        i-=i&-i;
    }
    return r;
}

void dfs(int c, bool keep)
{
    if (e[c][0]==0)
    {
        if (keep==0)
            return;
        update(a[tin[c]],1);
        return;
    }
    int x=0,y=0;
    ll z=0;
    if (tout[e[c][0]]-tin[e[c][0]]<tout[e[c][1]]-tin[e[c][1]])
        x=1;
    else
        y=1;
    dfs(e[c][y],0);
    dfs(e[c][x],1);
    for (int i=tin[e[c][y]];i<tout[e[c][y]];++i)
        z+=query(a[i]);
    ans+=min(z,1LL*(tout[e[c][0]]-tin[e[c][0]])*(tout[e[c][1]]-tin[e[c][1]])-z);
    if (keep==0)
        for (int i=tin[e[c][x]];i<tout[e[c][x]];++i)
            update(a[i],-1);
    else
        for (int i=tin[e[c][y]];i<tout[e[c][y]];++i)
            update(a[i],1);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n;
    dfs();
    dfs(0,1);
    cout<<ans;
    return 0;
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	320 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	716 KB	Output is correct
2	Correct	3 ms	460 KB	Output is correct
3	Correct	2 ms	712 KB	Output is correct
4	Correct	2 ms	844 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1616 KB	Output is correct
2	Correct	7 ms	844 KB	Output is correct
3	Correct	18 ms	1744 KB	Output is correct
4	Correct	6 ms	1612 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	2636 KB	Output is correct
2	Correct	23 ms	4004 KB	Output is correct
3	Correct	25 ms	5320 KB	Output is correct
4	Correct	24 ms	5320 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	9932 KB	Output is correct
2	Correct	34 ms	7492 KB	Output is correct
3	Correct	37 ms	5904 KB	Output is correct
4	Correct	34 ms	4704 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	6072 KB	Output is correct
2	Correct	43 ms	7492 KB	Output is correct
3	Correct	45 ms	10264 KB	Output is correct
4	Correct	44 ms	10168 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	104 ms	11536 KB	Output is correct
2	Correct	87 ms	10180 KB	Output is correct
3	Correct	69 ms	10308 KB	Output is correct
4	Correct	81 ms	9436 KB	Output is correct
5	Correct	105 ms	8276 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	75 ms	10244 KB	Output is correct
2	Correct	92 ms	15940 KB	Output is correct
3	Correct	88 ms	14196 KB	Output is correct
4	Correct	75 ms	17068 KB	Output is correct
5	Correct	125 ms	9420 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	80 ms	9980 KB	Output is correct
2	Correct	78 ms	11712 KB	Output is correct
3	Correct	114 ms	9840 KB	Output is correct
4	Correct	83 ms	10180 KB	Output is correct
5	Correct	74 ms	17476 KB	Output is correct
6	Correct	144 ms	9696 KB	Output is correct

Submission #404143

Compilation message