Submission #708374

#	Time	Username	Problem	Language	Result	Execution time	Memory
708374		doowey	Ants and Sugar (JOI22_sugar)	C++14	100 / 100	3497 ms	108664 KiB

sugar

#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
const int N = (int)5e5 + 10;
int typ[N];
int X[N];
int A[N];
 
struct Node{
    ll dp[2][2][2]; // [start][end][x_cnt]
    ll lazy_x;
    ll lazy_both;
};
 
void upd(ll &a, ll b){
    a = max(a, b);
}
 
Node make_node(){
    Node r;
    for(int i = 0 ; i < 2; i ++ ){
        for(int j = 0; j < 2; j ++ ){
            for(int k = 0 ;k < 2; k ++ ){
                r.dp[i][j][k] = -(ll)1e18;
            }
        }
    }
    r.lazy_x = 0ll;
    r.lazy_both = 0ll;
    return r;
}
 
const Node D = make_node();
 
Node unite(Node aa, Node bb){
    Node res = aa;
    int cum;
    for(int st = 0 ; st < 2; st ++ ){
        for(int en = 0; en < 2; en ++ ){
            for(int p = 0; p < 2; p ++ ){
                for(int q = 0; q < 2; q ++ ){
                    upd(res.dp[st][en][1], aa.dp[st][0][p] + bb.dp[1][en][q]);
                    upd(res.dp[st][en][1], aa.dp[st][1][p] + bb.dp[0][en][q]);
                }
                upd(res.dp[st][en][p], bb.dp[st][en][p]);
            }
        }
    }
    return res;
}
 
Node T[N * 4 + 512];
 
void push(int node, int cl, int cr){
    for(int f = 0; f < 2; f ++ ){
        for(int c = 0; c < 2; c ++ ){
            if(f == 0) T[node].dp[f][f][c] -= T[node].lazy_both;
            else T[node].dp[f][f][c] += T[node].lazy_both;
            for(int s = 0 ; s < 2; s ++ ){
                T[node].dp[f][s][c] += (c + (f + s == 2)) * 1ll * T[node].lazy_x;
            }
        }
    }
    if(cl != cr){
        T[node * 2].lazy_x += T[node].lazy_x;
        T[node * 2 + 1].lazy_x += T[node].lazy_x;
        T[node * 2].lazy_both += T[node].lazy_both;
        T[node * 2 + 1].lazy_both += T[node].lazy_both;
    }
    T[node].lazy_x = T[node].lazy_both = 0;
}
 
void update(int node, int cl, int cr, int tl, int tr, int Xi, int Yi){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        if(Xi == Yi){
            T[node].lazy_both = Xi;
        }
        else{
            T[node].lazy_x = Xi;
        }
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2ll;
    update(node * 2, cl, mid, tl, tr, Xi, Yi);
    update(node * 2 + 1, mid + 1, cr, tl, tr, Xi, Yi);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}
 
int k;
vector<int> posi;
void perform_update(int tl, int tr, int Xi, int Yi){
    int ii = lower_bound(posi.begin(), posi.end(), tl) - posi.begin();
    int jj = lower_bound(posi.begin(), posi.end(), tr + 1) - posi.begin();
    jj -- ;
    //cout << ii << " " << jj << " | " << Xi << " " << Yi << "\n";
    if(ii <= jj)
        update(1, 0, k - 1, ii, jj, Xi, Yi);
}
 
void build(int node, int cl, int cr){
    T[node] = D;
    if(cl == cr){
        T[node].dp[0][0][0] = 0;
        T[node].dp[0][1][1] = 0;
        T[node].dp[1][1][0] = 0;
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}
 
ll get_max(){
    ll V = 0ll;
    V = max(V, T[1].dp[0][1][1]);
    return V;
}
 
int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int q, d;
    cin >> q >> d;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> typ[iq] >> X[iq] >> A[iq];
        posi.push_back(X[iq]);
    }
    sort(posi.begin(), posi.end());
    posi.resize(unique(posi.begin(), posi.end()) - posi.begin());
    k = posi.size();
    
    build(1, 0, k - 1);
    ll ants = 0ll;
    for(int iq = 1; iq <= q; iq ++ ){
        if(typ[iq] == 1){
            perform_update(X[iq] + 1, (int)1e9, A[iq], A[iq]);
            perform_update(X[iq], X[iq], A[iq], 0);
            ants += A[iq];
        }
        else{
            perform_update(X[iq] + d + 1, (int)1e9, -A[iq], -A[iq]);
            perform_update(X[iq] - d, X[iq] + d, -A[iq], 0);
        }
        cout << ants - get_max() << "\n";
 
    }
    return 0;
}

Compilation message (stderr)

sugar.cpp: In function 'Node unite(Node, Node)':
sugar.cpp:46:9: warning: unused variable 'cum' [-Wunused-variable]
   46 |     int cum;
      |         ^~~

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