oj.uz

답안 #404143

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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