oj.uz

답안 #863460

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
863460 2023-10-20T11:43:59 Z Bolatulu Tree Rotations (POI11_rot) C++17
100 / 100
 719 ms 44228 KB 
// Bolatulu
#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define int long long
#define kanagattandirilmagandiktarinizdan ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define pb push_back
#define F first
#define S second
#define md (tl+tr)/2
#define TL v+v,tl,mid
#define TR v+v+1,mid+1,tr

#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

using namespace std;

int binpow(int a,int n,int M) {
    if (n==0)
        return 1;
    if (n%2!=0)
        return (a * binpow(a,n-1,M))%M;
    int z=binpow(a,n/2,M);
    return (z*z)%M;
}

const ll INF = 1e18;
const int N =  1e6+7;
const int M = 1e9+7;
const ll HZ = 1e5;
const int MAX = INT_MAX;
const int MIN = INT_MIN;
const db pi = 3.141592653;
const int P=31;

int sz[N],n,a[N],l[N],r[N],tame=1,ans,t[N];
vector <int> d, s;

void upd(int v,int tl,int tr,int pos,bool add) {
    if (tl==tr) {
        if (add)
            t[v]++;
        else
            t[v]=0;
        return;
    }
    if (pos<=md)
        upd(v+v,tl,md,pos,add);
    else
        upd(v+v+1,md+1,tr,pos,add);
    t[v]=t[v+v]+t[v+v+1];
}

int get(int v,int tl,int tr,int l,int r) {
    if (tl>=l and tr<=r)
        return t[v];
    if (tl>r or tr<l)
        return 0;
    return get(v+v,tl,md,l,r)+get(v+v+1,md+1,tr,l,r);
}

void read(int v) {
    int z;
    cin >> z;
    sz[v] = 1;
    if (z) {
        a[v] = z;
        return;
    }
    l[v] = ++tame;
    read(l[v]);
    sz[v] += sz[l[v]];
    r[v] = ++tame;
    read(r[v]);
    sz[v] += sz[r[v]];
}

void add(int v) {
    if (!l[v]) {
        d.push_back(a[v]);
        return;
    }
    add(l[v]), add(r[v]);
}

void add1(int v) {
    if (!l[v]) {
        upd(1,1,n,a[v],1);
        s.push_back(a[v]);
        return;
    }
    add1(l[v]), add1(r[v]);
}

void gett(int v,bool cl=0,bool dir=0) {
    if (!l[v]) {
        if (!cl) {
            if (!dir)
                d.push_back(a[v]);
            else {
                upd(1,1,n,a[v],1);
                s.push_back(a[v]);
            }
        }
        return;
    }
    if (sz[l[v]]>sz[r[v]])
        swap(l[v],r[v]);
    gett(l[v],1,0), gett(r[v],0,1);
    add(l[v]);
    int sum1=0,sum2=0;
    for (auto now : d) {
        if (now>1)
            sum1 += get(1, 1, n, 1, now - 1);
        if (now<n)
            sum2 += get(1, 1, n, now + 1, n);
    }
    ans+=min(sum1,sum2);
    if (cl) {
        d.clear();
        for (auto now: s)
            upd(1, 1, n, now, 0);
        s.clear();
    } else {
        if (!dir) {
            add(r[v]);
            for (auto now: s)
                upd(1, 1, n, now, 0);
            s.clear();
        } else {
            add1(l[v]);
            d.clear();
        }
    }
}

void solve() {
    cin >> n;
    read(1);
    gett(1);
    cout << ans;
}

signed main() {
    // freopen("lca.in", "r", stdin);
    // freopen("lca.out", "w", stdout);
    kanagattandirilmagandiktarinizdan
    int test = 1, count = 1;
    // cin >> test;
    while (test--) {
        // cout << "Case " << count << ":\n";
        solve();
        if (test) {
            cout << '\n';
        }
        count++;
    }
    return 0;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10588 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 1 ms 10840 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 11100 KB Output is correct
2 Correct 7 ms 10844 KB Output is correct
3 Correct 3 ms 11100 KB Output is correct
4 Correct 3 ms 11312 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14428 KB Output is correct
2 Correct 26 ms 13024 KB Output is correct
3 Correct 74 ms 11556 KB Output is correct
4 Correct 14 ms 12120 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 14828 KB Output is correct
2 Correct 56 ms 16944 KB Output is correct
3 Correct 78 ms 18816 KB Output is correct
4 Correct 64 ms 18508 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 28880 KB Output is correct
2 Correct 95 ms 25708 KB Output is correct
3 Correct 136 ms 21600 KB Output is correct
4 Correct 101 ms 21956 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 23812 KB Output is correct
2 Correct 143 ms 26008 KB Output is correct
3 Correct 112 ms 30672 KB Output is correct
4 Correct 116 ms 29908 KB Output is correct

Subtask #9
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 491 ms 33248 KB Output is correct
2 Correct 267 ms 32128 KB Output is correct
3 Correct 264 ms 32728 KB Output is correct
4 Correct 332 ms 30780 KB Output is correct
5 Correct 556 ms 27924 KB Output is correct

Subtask #10
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 282 ms 31556 KB Output is correct
2 Correct 271 ms 41128 KB Output is correct
3 Correct 341 ms 37288 KB Output is correct
4 Correct 202 ms 43088 KB Output is correct
5 Correct 669 ms 29960 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 269 ms 31388 KB Output is correct
2 Correct 242 ms 34824 KB Output is correct
3 Correct 544 ms 31780 KB Output is correct
4 Correct 303 ms 31556 KB Output is correct
5 Correct 205 ms 44228 KB Output is correct
6 Correct 719 ms 30404 KB Output is correct