oj.uz

Submission #1105927

# Submission time Handle Problem Language Result Execution time Memory
1105927 2024-10-28T12:47:50 Z vjudge1 Tree Rotations (POI11_rot) C++17
63 / 100
 36 ms 21484 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[200005],en[200005],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 6480 KB Output is correct
2 Correct 1 ms 6480 KB Output is correct
3 Correct 1 ms 6480 KB Output is correct
4 Correct 1 ms 6480 KB Output is correct
5 Correct 1 ms 6480 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7248 KB Output is correct
2 Correct 7 ms 6736 KB Output is correct
3 Correct 16 ms 9204 KB Output is correct
4 Correct 5 ms 6992 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 9552 KB Output is correct
2 Correct 18 ms 10452 KB Output is correct
3 Correct 19 ms 11100 KB Output is correct
4 Correct 20 ms 11460 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 13648 KB Output is correct
2 Correct 27 ms 12624 KB Output is correct
3 Correct 36 ms 11220 KB Output is correct
4 Correct 27 ms 10980 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 28 ms 20816 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 20304 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 21484 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 30 ms 21076 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -