oj.uz

Submission #1102785

# Submission time Handle Problem Language Result Execution time Memory
1102785 2024-10-18T22:08:40 Z raphaelp Tree Rotations (POI11_rot) C++14
0 / 100
 144 ms 60492 KB 
#include <bits/stdc++.h>
using namespace std;

class SegTree
{
private:
    vector<int> st, lef, rig;
    int N, buff = 2;
    int l(int x)
    {
        if (lef[x] == -1)
        {
            lef[x] = buff++;
            lef.push_back(-1);
            rig.push_back(-1);
            st.push_back(0);
        }
        return lef[x];
    }
    int r(int x)
    {
        if (rig[x] == -1)
        {
            rig[x] = buff++;
            lef.push_back(-1);
            rig.push_back(-1);
            st.push_back(0);
        }
        return rig[x];
    }
    void add(int L, int R, int a, int x)
    {
        if (L > a || R < a)
            return;
        if (L == a && R == a)
        {
            st[x] = 1;
        }
        else
        {
            int m = (L + R) / 2;
            add(L, m, a, l(x));
            add(m + 1, R, a, r(x));
            st[x] = st[l(x)] + st[r(x)];
        }
    }
    int sum(int L, int R, int a, int b, int x)
    {
        if (L > b || R < a)
            return 0;
        if (L >= a && R <= b)
            return st[x];
        int m = (L + R) / 2;
        return sum(L, m, a, b, l(x)) + sum(m + 1, R, a, b, r(x));
    }

public:
    SegTree(int x)
    {
        N = pow(2, ceil(log2(N)));
        st.assign(2, 0);
        lef.assign(2, -1);
        rig.assign(2, -1);
    }
    void add(int x) { add(0, N - 1, x, 1); }
    int sum(int a, int b) { return sum(0, N - 1, a, b, 1); }
};

int read(int N, long long &buff, long long &tot, SegTree &C, vector<int> &Tab)
{
    int next;
    cin >> next;
    if (next)
    {
        Tab.push_back(next);
        C.add(next);
        return next;
    }
    next = buff++;
    SegTree A(N), B(N);
    vector<int> Tab2, Tab3;
    read(N, buff, tot, A, Tab2);
    read(N, buff, tot, B, Tab3);
    if (Tab2.size() > Tab3.size())
    {
        swap(Tab2, Tab3);
        swap(A, B);
    }
    int score1 = 0, score2 = 0;
    for (auto val : Tab2)
    {
        score1 += B.sum(0, val);
        score2 += B.sum(val, N - 1);
        Tab3.push_back(val);
    }
    tot += min(score1, score2);
    for (auto val : Tab2)
        B.add(val);
    swap(Tab3, Tab);
    swap(B, C);

    return next;
}
int main()
{
    int N;
    cin >> N;
    int N2 = N * 2 - 1;
    vector<vector<int>> AR(N2);
    long long buff = N, tot = 0;
    N++;
    SegTree temp(N);
    vector<int> Tab;
    read(N, buff, tot, temp, Tab);
    cout << tot;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 504 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 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

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

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 10.0

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