Submission #1102786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102786		raphaelp	Untitled (POI11_rot)	C++14	54 / 100	1044 ms	65536 KiB

Main

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10