oj.uz

Submission #1087303

# Submission time Handle Problem Language Result Execution time Memory
1087303 2024-09-12T13:18:20 Z anarch_y Tree Rotations (POI11_rot) C++17
0 / 100
 474 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> 
using index_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int maxn = 400001;
vector<int> adj[maxn];
int A[maxn];
index_set<int> T[maxn];
ll ans = 0LL;

void dfs(int s){
    if(sz(adj[s]) == 0){
        T[s].insert(A[s]);
        return;
    }
    int u1 = adj[s][0], u2 = adj[s][1];
    dfs(u1); dfs(u2);
    if(sz(T[u1]) < sz(T[u2])) swap(u1, u2);
    int m1 = 0, m2 = 0;
    for(auto e: T[u2]){
        int x = T[u1].order_of_key(e);
        m1 += x;
        m2 += sz(T[u1])-x;
    }
    ans += (ll)min(m1, m2);
    for(auto e: T[u2]){
        T[u1].insert(e);
    }
    T[u2].clear();
    T[s].swap(T[u1]);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    int cur = 0;
    vector<int> v;
    while(cur < n){
        int x; cin >> x;
        v.pb(x);
        if(x != 0) cur++;
    }
    stack<int> s;
    for(int i=1; i<=sz(v); i++){
        int x = v[i-1];
        if(!s.empty()){
            adj[s.top()].pb(i);
        }
        s.push(i);
        if(x != 0){
            A[i] = x;
            s.pop();
        }
        if(!s.empty() and sz(adj[s.top()]) == 2) s.pop();
    }
    dfs(1);
    cout << ans;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 9.0

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

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 54 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 310 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 474 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -