oj.uz

Submission #1020730

# Submission time Handle Problem Language Result Execution time Memory
1020730 2024-07-12T08:57:26 Z kustizus Tree Rotations (POI11_rot) C++17
0 / 100
 22 ms 9936 KB 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,fma,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=2e5;
vector <int> v;
pair <int,int> mp[2*N+5];
int n,x,idx=0,cnt[2*N+5],sz[2*N+5],sum[2*N+5],FT[N+5];
void Back(int pos){
    if (!v.back()){
        v.pop_back();
        if (!mp[pos].first){
            mp[pos].first=++idx;
            Back(idx);
            Back(pos);
            return;
        }
        else mp[pos].second=++idx;
        Back(idx);
    }
    else{
        if (!mp[pos].first){
            cnt[idx]=v.back();
            v.pop_back();
        }
        else{
            mp[pos].second=++idx;
            cnt[idx]=v.back();
            v.pop_back();
        }
    }
}
void dfs(int i){
    if (cnt[i]){
        sz[i]=1;
        return;
    }
    int x=mp[i].first;
    int y=mp[i].second;
    sz[i]=sz[x]+sz[y];
}
void Update(int pos, int val){
    for (;pos<=n;pos+=pos&(-pos)) FT[pos]+=val;
}
int Get(int pos){
    int val=0;
    for (;pos;pos-=pos&(-pos)) val+=FT[pos];
    return val;
}
void cl(int i, int val){
    if (cnt[i]){
        Update(cnt[i],val);
        return;
    }
    int x=mp[i].first;
    int y=mp[i].second;
    cl(x,val);
    cl(y,val);
}
int lh,nh;
void Cal(int i){
    if (cnt[i]){
        lh+=Get(cnt[i]);
        nh+=Get(n)-Get(cnt[i]);
        return;
    }
    int x=mp[i].first;
    int y=mp[i].second;
    Cal(x);
    Cal(y);
}
void dfs1(int i){
    if (cnt[i]){
        Update(cnt[i],1);
        return;
    }
    int x=mp[i].first;
    int y=mp[i].second;
    if (sz[x]>sz[y]) swap(x,y);
    dfs1(x);
    sum[i]+=sum[x];
    cl(x,-1);
    dfs1(y);
    sum[i]+=sum[y];
    lh=nh=0;
    Cal(x);
    cl(x,1);
    sum[i]+=min(lh,nh);
}
void Solve(){
    cin>>n;
    while (cin>>x) v.push_back(x);
    reverse(v.begin(),v.end());
    Back(0);
    dfs(0);
    dfs1(0);
    cout<<sum[0];
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen ("FILE.INP","r",stdin);
    // freopen ("FILE.OUT","w",stdout);
    int t=1;
    // cin>>t;
    while (t--) Solve();
    cerr<<"\nTIME: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 9.0

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

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 10.0

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