Submission #1058030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058030		mickey080929	Heavy Light Decomposition (CCO24_day2problem2)	C++17	25 / 25	840 ms	94292 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

const ll mod = 1000003;

struct Node{
    ll mn, sum;
};

Node Merge(Node u, Node v) {
    Node ret;
    ret.mn = min(u.mn, v.mn);
    ret.sum = 0;
    if (u.mn == ret.mn) ret.sum += u.sum;
    if (v.mn == ret.mn) ret.sum += v.sum;
    ret.sum %= mod;
    return ret;
}

struct SegmentTree{
    vector<Node> tree;
    vector<ll> lazy;
    void init(ll n) {
        int sz = 1 << __lg(n-1) + 2;
        tree.assign(sz, {0, 0});
        lazy.assign(sz, 0);
    }
    void propagate(ll node, ll s, ll e) {
        if (!lazy[node]) return;
        tree[node].mn += lazy[node];
        if (s != e) {
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        lazy[node] = 0;
    }
    void update(ll node, ll s, ll e, ll l, ll r, ll v) {
        propagate(node, s, e);
        if (l > e || s > r) return;
        if (l <= s && e <= r) {
            lazy[node] = v;
            propagate(node, s, e);
            return;
        }
        ll mid = s + e >> 1;
        update(node*2, s, mid, l, r, v);
        update(node*2+1, mid+1, e, l, r, v);
        tree[node] = Merge(tree[node*2], tree[node*2+1]);
    }
    void modify(ll node, ll s, ll e, ll tar, ll val) {
        propagate(node, s, e);
        if (s > tar || tar > e) return;
        if (s == e) {
            tree[node].sum += val;
            tree[node].sum %= mod;
            return;
        }
        ll mid = s + e >> 1;
        modify(node*2, s, mid, tar, val);
        modify(node*2+1, mid+1, e, tar, val);
        tree[node] = Merge(tree[node*2], tree[node*2+1]);
    }
    ll Get() {
        if (tree[1].mn == 0) return tree[1].sum;
        return 0;
    }
};

ll a[500010];
ll dp[500010];
SegmentTree seg[2];
vector<ll> pos[500010];

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    ll N;
    cin >> N;
    for (ll i=1; i<=N; i++) {
        cin >> a[i];
        pos[i].push_back(0);
    }
    seg[0].init(N);
    seg[1].init(N);
    dp[0] = 1;
    seg[0].modify(1, 1, N, 1, 1);
    seg[1].modify(1, 1, N, 1, 1);
    for (ll i=1; i<=N; i++) {
        ll v = a[i];
        seg[i&1].update(1, 1, N, 1, pos[v].back(), 1);
        if (pos[v].back() % 2 != i % 2) {
            seg[i&1^1].update(1, 1, N, 1, i, 1);
        }
        else {
            seg[i&1^1].update(1, 1, N, pos[v].back()+1, i, 1);
            if (pos[v].size() >= 2) {
                seg[i&1^1].update(1, 1, N, pos[v][pos[v].size()-2]+1, pos[v].back(), -1);
            }
        }
        pos[v].push_back(i);
        dp[i] = (seg[0].Get() + seg[1].Get()) % mod;
        if (i < N) {
            seg[0].modify(1, 1, N, i+1, dp[i]);
            seg[1].modify(1, 1, N, i+1, dp[i]);
        }
    }
    cout << dp[N] << '\n';
}

Compilation message (stderr)

Main.cpp: In member function 'void SegmentTree::init(ll)':
Main.cpp:27:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   27 |         int sz = 1 << __lg(n-1) + 2;
      |                       ~~~~~~~~~~^~~
Main.cpp: In member function 'void SegmentTree::update(ll, ll, ll, ll, ll, ll)':
Main.cpp:48:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         ll mid = s + e >> 1;
      |                  ~~^~~
Main.cpp: In member function 'void SegmentTree::modify(ll, ll, ll, ll, ll)':
Main.cpp:61:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |         ll mid = s + e >> 1;
      |                  ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:94:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   94 |             seg[i&1^1].update(1, 1, N, 1, i, 1);
      |                 ~^~
Main.cpp:97:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   97 |             seg[i&1^1].update(1, 1, N, pos[v].back()+1, i, 1);
      |                 ~^~
Main.cpp:99:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   99 |                 seg[i&1^1].update(1, 1, N, pos[v][pos[v].size()-2]+1, pos[v].back(), -1);
      |                     ~^~

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