Submission #1340776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1340776		SpyrosAliv	Snacks (NOI25_snacks)	C++20	100 / 100	400 ms	28592 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e15;

void solve() {
    int n, q; cin >> n >> q;
    int s = 0;
    map<int, int> cnt;
    set<int> act;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        cnt[x]++;
        act.insert(x);
        s += x;
    }
    act.insert(INF);
    cout << s << "\n";
    while (q--) {
        int l, r, x; cin >> l >> r >> x;
        int rem = 0;
        while (true) {
            auto nxt = act.lower_bound(l);
            if (*nxt > r) break;
            rem += cnt[*nxt];
            s -= *nxt * cnt[*nxt];
            cnt[*nxt] = 0;
            act.erase(nxt);
        }
        s += x * rem;
        act.insert(x);
        cnt[x] += rem;
        cout << s << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while (t--) solve();
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 21 / 21
• Subtask 4: 13 / 13
• Subtask 5: 16 / 16
• Subtask 6: 33 / 33