oj.uz

답안 #862173

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862173 2023-10-17T15:50:29 Z vjudge1 Tree Rotations (POI11_rot) C++17
0 / 100
 1000 ms 34364 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 =  2e5+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 n,l[N],r[N],t=1,a[N],sz[N],ans[N];
vector <int> d[2];
vector <vector <int>> g(2,vector <int> (N));

void clear(int v,int tl,int tr) {
    if (tl==tr) {
        g[0][v]=0;
        g[1][v]=0;
        return;
    }
    clear(v+v,tl,md), clear(v+v+1,md+1,tr);
    g[0][v]=0;
    g[1][v]=0;
}

void upd(int v,int tl,int tr,int pos,int dir) {
    if (tl == tr) {
        g[dir][v]++;
        return;
    }
    if (pos <= md)
        upd(v + v, tl, md, pos, dir);
    else
        upd(v + v + 1, md + 1, tr, pos, dir);
    g[dir][v] = g[dir][v + v], g[dir][v + v + 1];
}

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

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

int calc1(int v, bool rev) {
    int x = 0;
    for (auto now : d[0]) {
        if (!rev) {
            if (now > 1)
                x += get(1, 1, n, 1, now - 1, 1);
        } else {
            if (now < n)
                x += get(1, 1, n, now + 1, n, 1);
        }
    }
    return x;
}

int calc2(int v, bool rev) {
    int x = 0;
    for (auto now : d[1]) {
        if (rev) {
            if (now > 1)
                x += get(1, 1, n, 1, now - 1, 0);
        } else {
            if (now < n)
                x += get(1, 1, n, now + 1, n, 0);
        }
    }
    return x;
}

void get(int v,int dir) {
    if (a[v]) {
        d[dir] = {a[v]};
        upd(1, 1, n, a[v], dir);
        ans[v] = 0;
        return;
    }
    int L, R;
    vector <int> vv;
    if (sz[l[v]]<=sz[r[v]]) {
        get(l[v],0);
        swap(vv,d[0]);
        clear(1,1,n);
        get(r[v],1);
        swap(vv,d[0]);
        L = calc1(v, false), R = calc1(v, true);
    } else {
        get(r[v],1);
        swap(vv,d[1]);
        clear(1,1,n);
        get(l[v],0);
        swap(vv,d[1]);
        L = calc2(v, false), R = calc2(v, true);
    }
    ans[v] += min(L, R);
    ans[v] += ans[l[v]] + ans[r[v]];
    if (v == 1)
        return;
    if (d[0].size() < d[1].size())
        d[0].swap(d[1]), g[0].swap(g[1]);
    for (auto now: d[1])
        d[0].push_back(now), upd(1, 1, n, now, 0);
    d[dir].swap(d[0]), g[dir].swap(g[0]);
}

void solve() {
    cin >> n;
    read(1);
    get(1, 0);
    cout << ans[1];
}

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
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 9536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 9536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 9788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 10316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 441 ms 12084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1050 ms 11192 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 28 ms 34364 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 23 ms 23500 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 22 ms 23380 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 25 ms 25420 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 29 ms 24640 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -