oj.uz

Submission #1105929

# Submission time Handle Problem Language Result Execution time Memory
1105929 2024-10-28T12:48:54 Z vjudge1 Tree Rotations (POI11_rot) C++17
100 / 100
 166 ms 22600 KB 
#include <bits/stdc++.h>
#define ll long long
const ll mod=1e9+7;
#define fi first
#define se second
using namespace std;
int st[4000005],en[4000005],n,N=1,a[200005],nn,u,l[4000005],r[4000005];
int bit[200005];
void update(int u,int v)
{
    int idx=u;
    while (idx<=n)
    {
        bit[idx]+=v;
        idx+=(idx&(-idx));
    }
}
int getSum(int u)
{
    if (u==0) return 0;
    int idx=u,tong=0;
    while (idx>0)
    {
        tong+=bit[idx];
        idx-=(idx&(-idx));
    }
    return tong;
}
int get(int l,int r)
{
    return getSum(r)-getSum(l-1);
}
void solve()
{
    int hao=N;
    cin>>u;
    if (u!=0)
    {
        nn++;
        a[nn]=u;
        st[hao]=nn;
        en[hao]=nn;
    }
    else
    {
        int le=N+1;
        N++;
        solve();
        int ri=N+1;
        N++;
        solve();
        st[hao]=st[le];
        en[hao]=en[ri];
        l[hao]=le;
        r[hao]=ri;
    }
}
ll dfs(int u)
{
    ll ketqua=0,maxx1=0,maxx2=0;
    if (st[u]==en[u])
    {
        update(a[st[u]],1);
        return 0;
    }
    int le=l[u];
    int ri=r[u];
    if (en[ri]-st[ri]<en[le]-st[le]) swap(le,ri);
    ketqua+=dfs(le);
    for (int i=st[le];i<=en[le];++i)
    {
        update(a[i],-1);
    }
    ketqua+=dfs(ri);
    for (int i=st[le];i<=en[le];++i)
    {
        maxx1+=getSum(a[i]-1);
        maxx2+=get(a[i]+1,n);
    }
    for (int i=st[le];i<=en[le];++i)
    {
        update(a[i],1);
    }
    return ketqua+min(maxx1,maxx2);
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    solve();
    cout<<dfs(1);
    
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9040 KB Output is correct
2 Correct 5 ms 8584 KB Output is correct
3 Correct 15 ms 12892 KB Output is correct
4 Correct 5 ms 9040 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12880 KB Output is correct
2 Correct 16 ms 13648 KB Output is correct
3 Correct 17 ms 14416 KB Output is correct
4 Correct 17 ms 14404 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16464 KB Output is correct
2 Correct 23 ms 14928 KB Output is correct
3 Correct 28 ms 13904 KB Output is correct
4 Correct 25 ms 13136 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 14928 KB Output is correct
2 Correct 30 ms 16744 KB Output is correct
3 Correct 35 ms 18512 KB Output is correct
4 Correct 33 ms 17744 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 16972 KB Output is correct
2 Correct 71 ms 16968 KB Output is correct
3 Correct 51 ms 16200 KB Output is correct
4 Correct 70 ms 16720 KB Output is correct
5 Correct 113 ms 15952 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 17992 KB Output is correct
2 Correct 67 ms 22076 KB Output is correct
3 Correct 81 ms 20712 KB Output is correct
4 Correct 62 ms 21832 KB Output is correct
5 Correct 155 ms 18080 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 17744 KB Output is correct
2 Correct 60 ms 18104 KB Output is correct
3 Correct 108 ms 16972 KB Output is correct
4 Correct 75 ms 17488 KB Output is correct
5 Correct 55 ms 22600 KB Output is correct
6 Correct 166 ms 17936 KB Output is correct