Submission #632956

#	Time	Username	Problem	Language	Result	Execution time	Memory
632956		qwerasdfzxcl	Ants and Sugar (JOI22_sugar)	C++14	100 / 100	2400 ms	133896 KiB

sugar

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const ll INF = 4e18;

struct P{
    ll x;
    int c;
    P(){}
    P(ll _x, int _c): x(_x), c(_c) {}
    bool operator < (const P &p) const{return x < p.x;}
    P operator + (const P &p) const{return P(x + p.x, c + p.c);}
};

struct Node{
    P ans[2][2];
    ll one[2][2];
    Node(){}
    Node(ll c, ll d){
        ans[0][0] = P(-c, 0);
        ans[0][1] = P(-INF, 0);
        ans[1][0] = P(-INF, 0);
        ans[1][1] = P(d, 1);

        one[0][0] = -c;
        one[0][1] = -INF;
        one[1][0] = -INF;
        one[1][1] = d;
    }

    void pcd(ll x){
        ans[0][0].x -= x;
        ans[1][1].x += x;
        one[0][0] -= x;
        one[1][1] += x;
    }

    void pd(ll x){
        assert(x<0);
        one[0][1] += x;
        one[1][0] += x;
        one[1][1] += x;

        for (int i=0;i<2;i++){
            for (int j=0;j<2;j++){
                assert(ans[i][j].c <= 2);
                ans[i][j].x += x * ans[i][j].c;

                if (ans[i][j].x < one[i][j]){
                    ans[i][j].x = one[i][j];
                    if (i || j) ans[i][j].c = 1;
                    else ans[i][j].c = 0;
                }
            }
        }
    }

    Node operator + (const Node &N) const{
        Node ret;
        for (int i=0;i<2;i++){
            for (int j=0;j<2;j++){
                ret.ans[i][j] = max(ans[i][j], N.ans[i][j]);
                ret.one[i][j] = max(one[i][j], N.one[i][j]);
                for (int k=0;k<2;k++) ret.ans[i][j] = max(ret.ans[i][j], ans[i][k] + N.ans[k^1][j]);
            }
        }

        ret.one[0][1] = max(ret.one[0][1], one[0][0] + N.one[1][1]);
        ret.one[1][0] = max(ret.one[1][0], one[1][1] + N.one[0][0]);
        return ret;
    }
};

struct Seg{
    Node tree[1101000];
    pair<ll, ll> lazy[1101000];
    void init(int i, int l, int r){
        lazy[i] = {0, 0};
        if (l==r) {tree[i] = Node(0, 0); return;}

        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    void propagate(int i, int l, int r){
        if (lazy[i].first) tree[i].pcd(lazy[i].first);
        if (lazy[i].second) tree[i].pd(lazy[i].second);

        if (l!=r){
            lazy[i<<1].first += lazy[i].first;
            lazy[i<<1].second += lazy[i].second;

            lazy[i<<1|1].first += lazy[i].first;
            lazy[i<<1|1].second += lazy[i].second;
        }

        lazy[i] = {0, 0};
    }
    void update1(int i, int l, int r, int s, int e, ll x){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i].first += x;
            propagate(i, l, r);
            return;
        }

        int m = (l+r)>>1;
        update1(i<<1, l, m, s, e, x); update1(i<<1|1, m+1, r, s, e, x);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
    void update2(int i, int l, int r, int s, int e, ll x){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i].second += x;
            propagate(i, l, r);
            return;
        }

        int m = (l+r)>>1;
        update2(i<<1, l, m, s, e, x); update2(i<<1|1, m+1, r, s, e, x);
        tree[i] = tree[i<<1] + tree[i<<1|1];
    }
}tree;

vector<int> C[3];
int T[500500], X[500500], A[500500], d;

int main(){
    int q;
    scanf("%d %d", &q, &d);
    for (int i=1;i<=q;i++){
        scanf("%d %d %d", T+i, X+i, A+i);
        C[T[i]].push_back(X[i]);
        C[T[i]].push_back(X[i]-1);
    }
    int ant = C[1].size()<C[2].size()?1:2;

    C[ant].push_back(0);

    sort(C[ant].begin(), C[ant].end());
    C[ant].erase(unique(C[ant].begin(), C[ant].end()), C[ant].end());

    int sz = C[ant].size();
    tree.init(1, 1, sz);

    ll cur = 0;
    for (int i=1;i<=q;i++){
        if (T[i]==ant){
            int idx = lower_bound(C[ant].begin(), C[ant].end(), X[i]) - C[ant].begin() + 1;
            tree.update1(1, 1, sz, idx, sz, A[i]);
            cur += A[i];
        }
        else{
            int idx1 = lower_bound(C[ant].begin(), C[ant].end(), X[i]-d) - C[ant].begin() + 1;
            int idx2 = lower_bound(C[ant].begin(), C[ant].end(), X[i]+d) - C[ant].begin() + 1;
            tree.update1(1, 1, sz, idx2, sz, -A[i]);
            tree.update2(1, 1, sz, idx1, idx2-1, -A[i]);
        }

        ll ans = cur - max(tree.tree[1].ans[0][1].x, 0LL);
        printf("%lld\n", ans);
    }
    return 0;
}

Compilation message (stderr)

sugar.cpp: In function 'int main()':
sugar.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |     scanf("%d %d", &q, &d);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sugar.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         scanf("%d %d %d", T+i, X+i, A+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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