Submission #639264

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
639264	2022-09-09T07:12:01 Z	puppy	Tree Rotations (POI11_rot)	C++17	63 / 100	414 ms	15272 KB

#include <bits/stdc++.h>
using namespace std;
int g[400005][2], N;
int s[400005], e[400005];
int arr[400005];

struct sumseg
{
    int sz;
    vector<int> tree;
    void reset(int siz){sz = siz; tree.resize(1<<((int)ceil(log2(siz))+1));}
    int init(int s, int e, int node, vector<int> &arr)
    {
        if(s==e) return tree[node] = arr[s];
        return tree[node] = init(s, (s+e)/2, 2*node, arr) + init((s+e)/2+1, e, 2*node+1, arr);
    }
    void upd(int s, int e, int node, int idx, int val)
    {
        if(e<idx||idx<s) return;
        if(s==e){
            tree[node] += val; return;
        }
        upd(s, (s+e)/2, 2*node, idx, val); upd((s+e)/2+1, e, 2*node+1, idx, val);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
    int query(int s, int e, int node, int l, int r)
    {
        if(e<l||r<s) return 0;
        if(l<=s&&e<=r) return tree[node];
        return query(s, (s+e)/2, 2*node, l, r) + query((s+e)/2+1, e, 2*node+1, l, r);
    }
}seg;

int pv;

void getTree(int v)
{
    int a; cin>>a;
    if(!a){
        g[v][0] = ++pv;
        getTree(g[v][0]);
    }
    else{
        g[v][0] = a;
    }
    int b; cin>>b;
    if(!b){
        g[v][1] = ++pv;
        getTree(g[v][1]);
    }
    else g[v][1] = b;
}

int ans = 0;
int pos;

void ett(int v)
{
    if(!v) return;
    s[v] = pos;
    if(v<=N){
        arr[pos++] = v;
    }
    ett(g[v][0]); ett(g[v][1]);
    e[v] = pos;
}

void dfs(int v, bool add)
{
    if(v<=N){
        if(add){
            seg.upd(1, N, 1, v, 1);
        }
        return;
    }
    int lsz = e[g[v][0]] - s[g[v][0]];
    int rsz = e[g[v][1]] - s[g[v][1]];
    if(lsz < rsz){
        dfs(g[v][0], false);
        dfs(g[v][1], true);
        //오른쪽만 남음
        int inv = 0;
        for(int i=s[g[v][0]];i<e[g[v][0]];i++){
            inv += seg.query(1, N, 1, arr[i]+1, N);
        }
        ans += min(inv, lsz*rsz-inv);
        if(add){
            for(int i=s[g[v][0]];i<e[g[v][0]];i++){
                seg.upd(1, N, 1, arr[i], 1);
            }
        }
        else{
            for(int i=s[g[v][1]];i<e[g[v][1]];i++){
                seg.upd(1, N, 1, arr[i], -1);
            }
        }
    }
    else{
        dfs(g[v][1], false);
        dfs(g[v][0], true);
        int inv = 0;
        for(int i=s[g[v][1]];i<e[g[v][1]];i++){
            inv += seg.query(1, N, 1, arr[i]+1, N);
        }
        ans += min(inv, lsz*rsz-inv);
        if(add){
            for(int i=s[g[v][1]];i<e[g[v][1]];i++){
                seg.upd(1, N, 1, arr[i], 1);
            }
        }
        else{
            for(int i=s[g[v][0]];i<e[g[v][0]];i++){
                seg.upd(1, N, 1, arr[i], -1);
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>N;
    int tt; cin>>tt;
    seg.reset(N+1);
    pv = N+1;
    getTree(N+1);
    ett(N+1);
    dfs(N+1, 0);
    cout<<ans;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	852 KB	Output is correct
2	Correct	6 ms	560 KB	Output is correct
3	Correct	3 ms	892 KB	Output is correct
4	Correct	3 ms	1024 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	2388 KB	Output is correct
2	Correct	23 ms	852 KB	Output is correct
3	Correct	64 ms	1620 KB	Output is correct
4	Correct	16 ms	1876 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	2652 KB	Output is correct
2	Correct	56 ms	5332 KB	Output is correct
3	Correct	69 ms	7372 KB	Output is correct
4	Correct	66 ms	7136 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	15272 KB	Output is correct
2	Correct	89 ms	10472 KB	Output is correct
3	Correct	131 ms	7204 KB	Output is correct
4	Correct	89 ms	5336 KB	Output is correct

Subtask #8
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	166 ms	6048 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	414 ms	14348 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	284 ms	11600 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	255 ms	11188 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Submission #639264

Compilation message