oj.uz

Submission #1102786

# Submission time Handle Problem Language Result Execution time Memory
1102786 2024-10-18T22:33:09 Z raphaelp Tree Rotations (POI11_rot) C++14
54 / 100
 1000 ms 65536 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(x)));
        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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 508 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 592 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 3 ms 852 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3408 KB Output is correct
2 Correct 13 ms 1108 KB Output is correct
3 Correct 9 ms 3412 KB Output is correct
4 Correct 10 ms 3924 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 10332 KB Output is correct
2 Correct 46 ms 2528 KB Output is correct
3 Correct 149 ms 5144 KB Output is correct
4 Correct 38 ms 8012 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 7852 KB Output is correct
2 Correct 167 ms 24140 KB Output is correct
3 Correct 186 ms 38840 KB Output is correct
4 Correct 179 ms 36412 KB Output is correct

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 19512 KB Output is correct
2 Correct 372 ms 46336 KB Output is correct
3 Runtime error 241 ms 65536 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 58448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 47912 KB Output is correct
2 Runtime error 112 ms 65536 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

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