제출 #1369514

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1369514		gohchingjayk	Snacks (NOI25_snacks)	C++20	100 / 100	769 ms	140100 KiB

Main

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

#define int ll

int n, q;
int a[200000 + 5];
int x[200000 + 5];
int l[200000 + 5];
int r[200000 + 5];
int mp[800000 + 5];

void discretise() {
    vector<int> disc;

    for (int i = 0; i < n; ++i) disc.emplace_back(a[i]);
    for (int i = 0; i < q; ++i) {
        disc.emplace_back(x[i]);
        disc.emplace_back(l[i]);
        disc.emplace_back(r[i]);
    }

    sort(disc.begin(), disc.end());
    unique(disc.begin(), disc.end());

    for (int i = 0; i < n; ++i) {
        int orig = a[i];
        a[i] = lower_bound(disc.begin(), disc.end(), orig) - disc.begin();
        mp[a[i]] = orig;
    }

    for (int i = 0; i < q; ++i) {
        int orig = x[i];
        x[i] = lower_bound(disc.begin(), disc.end(), orig) - disc.begin();
        mp[x[i]] = orig;
    }

    for (int i = 0; i < q; ++i) {
        int orig = l[i];
        l[i] = lower_bound(disc.begin(), disc.end(), orig) - disc.begin();
        mp[l[i]] = orig;
    }

    for (int i = 0; i < q; ++i) {
        int orig = r[i];
        r[i] = lower_bound(disc.begin(), disc.end(), orig) - disc.begin();
        mp[r[i]] = orig;
    }
}

struct Node {
    int l, r, m;
    Node *left = nullptr, *right = nullptr;
    bool lazy = false;
    int val = 0, val2 = 0;

    Node(int a, int b) {
        l = a, r = b, m = (l + r) / 2;
        if (a != b) {
            left = new Node(l, m);
            right = new Node(m + 1, r);
        }
    }

    void prop() {
        if (l == r) return;
        if (!lazy) return;
        lazy = false;
        left->val = 0;
        right->val = 0;
        left->val2 = 0;
        right->val2 = 0;
        left->lazy = true;
        right->lazy = true;
    }

    void range_zero(int a, int b) {
        if (r < a || b < l) {
            return;
        }

        if (a <= l && r <= b) {
            lazy = true;
            val = 0;
            val2 = 0;
            return;
        }

        prop();

        left->range_zero(a, b);
        right->range_zero(a, b);
        val = left->val + right->val;
        val2 = left->val2 + right->val2;
    }

    void point_update(int p, int v) {
        if (l == r) {
            val += v;
            val2 += v * mp[l];
            return;
        }

        prop();

        if (p <= m) left->point_update(p, v);
        else right->point_update(p, v);
        val = left->val + right->val;
        val2 = left->val2 + right->val2;
    }

    int range_sum(int a, int b) {
        if (r < a || b < l) {
            return 0;
        }

        if (a <= l && r <= b) {
            return val;
        }

        prop();

        return left->range_sum(a, b) + right->range_sum(a, b);
    }
};

Node *root;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> q;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < q; ++i) cin >> l[i] >> r[i] >> x[i];

    discretise();

    root = new Node(0, 800000 + 5);

    for (int i = 0; i < n; ++i) {
        root->point_update(a[i], 1);
    }

    cout << root->val2 << '\n';

    for (int i = 0; i < q; ++i) {
        int num = root->range_sum(l[i], r[i]);
        root->range_zero(l[i], r[i]);
        root->point_update(x[i], num);
        cout << root->val2 << '\n';
    }
}

• 서브태스크 0: 0 / 0
• 서브태스크 1: 5 / 5
• 서브태스크 2: 12 / 12
• 서브태스크 3: 21 / 21
• 서브태스크 4: 13 / 13
• 서브태스크 5: 16 / 16
• 서브태스크 6: 33 / 33