Submission #1096648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096648		raphaelp	Heavy Light Decomposition (CCO24_day2problem2)	C++14	25 / 25	1498 ms	34508 KiB

Main

#include <bits/stdc++.h>
using namespace std;
class SegTree
{
private:
    vector<int> st, nb, lazy;
    int N, MOD = 1000003;
    int r(int x) { return (x << 1) + 1; }
    int l(int x) { return (x << 1); }
    void propagate(int L, int R, int x)
    {
        st[x] += lazy[x];
        if (L != R)
        {
            lazy[r(x)] += lazy[x];
            lazy[l(x)] += lazy[x];
        }
        lazy[x] = 0;
    }
    void update(int L, int R, int a, int b, int val, int x)
    {
        propagate(L, R, x);
        if (L > b || R < a)
            return;
        if (L >= a && R <= b)
        {
            lazy[x] += val;
            propagate(L, R, x);
        }
        else
        {
            int m = (L + R) / 2;
            update(L, m, a, b, val, l(x));
            update(m + 1, R, a, b, val, r(x));
            st[x] = min(st[l(x)], st[r(x)]);
            nb[x] = (((st[l(x)] == st[x]) ? nb[l(x)] : 0) + ((st[r(x)] == st[x]) ? nb[r(x)] : 0)) % MOD;
        }
    }
    void set(int L, int R, int a, int val, int x)
    {
        propagate(L, R, x);
        if (L > a || R < a)
            return;
        if (L == a && R == a)
            nb[x] = val % MOD;
        else
        {
            int m = (L + R) / 2;
            set(L, m, a, val, l(x));
            set(m + 1, R, a, val, r(x));
            nb[x] = (((st[l(x)] == st[x]) ? nb[l(x)] : 0) + ((st[r(x)] == st[x]) ? nb[r(x)] : 0)) % MOD;
        }
    }
    int RSQ(int L, int R, int a, int b, int x)
    {
        propagate(L, R, x);
        if (L > b || R < a)
            return 0;
        if (st[x] != 0)
            return 0;
        if (L >= a && R <= b)
            return nb[x];
        int m = (L + R) / 2;
        return (RSQ(L, m, a, b, l(x)) + RSQ(m + 1, R, a, b, r(x))) % MOD;
    }

public:
    SegTree(int x)
    {
        N = pow(2, ceil(log2(x)));
        st.assign(2 * N, 0);
        nb.assign(2 * N, 0);
        lazy.assign(2 * N, 0);
    }
    void update(int a, int b, int val)
    {
        if (b >= a)
            update(0, N - 1, a, b, val, 1);
    }
    void set(int x, int val) { set(0, N - 1, x, val, 1); }
    int RSQ(int a, int b) { return RSQ(0, N - 1, a, b, 1); }
};
int main()
{
    int N;
    cin >> N;
    vector<int> Tab(N);
    for (int i = 0; i < N; i++)
    {
        cin >> Tab[i];
        Tab[i]--;
    }
    SegTree STodd(N + 1), STeven(N + 1);
    STodd.set(N, 1);
    STeven.set(N, 1);
    vector<int> last(N, N + 1), last2(N, -1);
    for (int i = N - 1; i >= 0; i--)
    {
        if (i % 2 == 1)
        {
            STeven.update(last[Tab[i]] + 1, N, 1);
            if (last[Tab[i]] % 2 == 0)
                STodd.update(last[Tab[i]] + 1, N, 10);
            else
                STodd.update(last[Tab[i]] + 1, last2[Tab[i]], -1);
            STodd.update(i + 1, last[Tab[i]], 1);
        }
        else
        {
            STodd.update(last[Tab[i]] + 1, N, 1);
            if (last[Tab[i]] % 2 == 1)
                STeven.update(last[Tab[i]] + 1, N, 10);
            else
                STeven.update(last[Tab[i]] + 1, last2[Tab[i]], -1);
            STeven.update(i + 1, last[Tab[i]], 1);
        }
        last2[Tab[i]] = last[Tab[i]];
        last[Tab[i]] = i;
        int tot = (STodd.RSQ(i, N) + STeven.RSQ(i, N)) % 1000003;
        STodd.set(i, tot);
        STeven.set(i, tot);
    }
    cout << (STodd.RSQ(1, N) + STeven.RSQ(1, N)) % 1000003;
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 5 / 5
• Subtask 4: 6 / 6
• Subtask 5: 7 / 7