Submission #791100

#	Time	Username	Problem	Language	Result	Execution time	Memory
791100		max0000561	Ants and Sugar (JOI22_sugar)	C++17	0 / 100	137 ms	38956 KiB

sugar

#include<bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()

using namespace std;

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int q, L;
    cin >> q >> L;
    vector<int> cnt(500500);
    vector<int> mx(500500);
    int ans = 0;
    vector<int> Q1(q), Q2(q);
    vector<vector<int>> ss;
    for (int i = 0; i < q; ++i) {
        int t, x, a;
        cin >> t >> x >> a;
        ss.push_back({t, x, a});
        x += 11;
        if (x % 2 == 1) {
            ans -= min(cnt[x], cnt[x + 1]);
            cnt[x] += a;
            ans += min(cnt[x], cnt[x + 1]);
        }
        else {
            ans -= min(cnt[x], cnt[x - 1]);
            cnt[x] += a;
            ans += min(cnt[x], cnt[x - 1]);
        }
        if (x % 2 == 1) {
            ans -= min(mx[x + 3], mx[x + 4]);
            ans -= min(mx[x + 1], mx[x + 2]);
            ans -= min(mx[x - 1], mx[x]);
            ans -= min(mx[x - 3], mx[x - 1]);

            mx[x] = max(0ll, cnt[x] - cnt[x + 1]);
            mx[x + 1] = max(0ll, cnt[x + 1] - cnt[x]);

            ans += min(mx[x + 3], mx[x + 4]);
            ans += min(mx[x + 1], mx[x + 2]);
            ans += min(mx[x - 1], mx[x]);
            ans += min(mx[x - 3], mx[x - 1]);
        }
        else {
            ans -= min(mx[x + 2], mx[x + 3]);
            ans -= min(mx[x], mx[x + 1]);
            ans -= min(mx[x - 2], mx[x - 1]);
            ans -= min(mx[x - 4], mx[x - 2]);

            mx[x] = max(0ll, cnt[x] - cnt[x - 1]);
            mx[x - 1] = max(0ll, cnt[x - 1] - cnt[x]);

            ans += min(mx[x + 2], mx[x + 3]);
            ans += min(mx[x], mx[x + 1]);
            ans += min(mx[x - 2], mx[x - 1]);
            ans += min(mx[x - 4], mx[x - 2]);
        }
        Q1[i] = ans;
    }
    fill(cnt.begin(), cnt.end(), 0);
    fill(mx.begin(), mx.end(), 0);
    ans = 0;
    for (int i = 0; i < q; ++i) {
        int t, x, a;
        t = ss[i][0];
        x = ss[i][1];
        a = ss[i][2];
        x += 9;
        if (x % 2 == 1) {
            ans -= min(cnt[x], cnt[x + 1]);
            cnt[x] += a;
            ans += min(cnt[x], cnt[x + 1]);
        }
        else {
            ans -= min(cnt[x], cnt[x - 1]);
            cnt[x] += a;
            ans += min(cnt[x], cnt[x - 1]);
        }
        if (x % 2 == 1) {
            ans -= min(mx[x + 3], mx[x + 4]);
            ans -= min(mx[x + 1], mx[x + 2]);
            ans -= min(mx[x - 1], mx[x]);
            ans -= min(mx[x - 3], mx[x - 1]);

            mx[x] = max(0ll, cnt[x] - cnt[x + 1]);
            mx[x + 1] = max(0ll, cnt[x + 1] - cnt[x]);

            ans += min(mx[x + 3], mx[x + 4]);
            ans += min(mx[x + 1], mx[x + 2]);
            ans += min(mx[x - 1], mx[x]);
            ans += min(mx[x - 3], mx[x - 1]);
        }
        else {
            ans -= min(mx[x + 2], mx[x + 3]);
            ans -= min(mx[x], mx[x + 1]);
            ans -= min(mx[x - 2], mx[x - 1]);
            ans -= min(mx[x - 4], mx[x - 2]);

            mx[x] = max(0ll, cnt[x] - cnt[x - 1]);
            mx[x - 1] = max(0ll, cnt[x - 1] - cnt[x]);

            ans += min(mx[x + 2], mx[x + 3]);
            ans += min(mx[x], mx[x + 1]);
            ans += min(mx[x - 2], mx[x - 1]);
            ans += min(mx[x - 4], mx[x - 2]);
        }
        Q2[i] = ans;
    }
    for (int i = 0; i < q; ++i) {
        cout << max(Q1[i], Q2[i]) << '\n';
    }
}

Compilation message (stderr)

sugar.cpp: In function 'int main()':
sugar.cpp:66:13: warning: variable 't' set but not used [-Wunused-but-set-variable]
   66 |         int t, x, a;
      |             ^

• Subtask 1: 0 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 26
• Subtask 4: 0 / 52