oj.uz

Submission #1105930

# Submission time Handle Problem Language Result Execution time Memory
1105930 2024-10-28T12:49:33 Z vjudge1 Tree Rotations (POI11_rot) C++17
100 / 100
 174 ms 21832 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 1 ms 8696 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 2 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 2 ms 8784 KB Output is correct
2 Correct 3 ms 8528 KB Output is correct
3 Correct 3 ms 8784 KB Output is correct
4 Correct 3 ms 8784 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9040 KB Output is correct
2 Correct 6 ms 8720 KB Output is correct
3 Correct 17 ms 12768 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 18 ms 13648 KB Output is correct
3 Correct 19 ms 14416 KB Output is correct
4 Correct 19 ms 14416 KB Output is correct

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 14928 KB Output is correct
2 Correct 33 ms 15964 KB Output is correct
3 Correct 31 ms 17744 KB Output is correct
4 Correct 30 ms 17756 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 16720 KB Output is correct
2 Correct 64 ms 16012 KB Output is correct
3 Correct 51 ms 16240 KB Output is correct
4 Correct 67 ms 15608 KB Output is correct
5 Correct 112 ms 14928 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 17744 KB Output is correct
2 Correct 65 ms 21072 KB Output is correct
3 Correct 77 ms 19784 KB Output is correct
4 Correct 59 ms 21832 KB Output is correct
5 Correct 148 ms 17052 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 17488 KB Output is correct
2 Correct 62 ms 17992 KB Output is correct
3 Correct 103 ms 16904 KB Output is correct
4 Correct 77 ms 17488 KB Output is correct
5 Correct 57 ms 21584 KB Output is correct
6 Correct 174 ms 16976 KB Output is correct