| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 708341 | doowey | Ants and Sugar (JOI22_sugar) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
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][3]; // [start][end][x_cnt]
ll lazy_x;
ll lazy_both;
int lef;
int rig;
};
void upd(ll &a, ll b){
a = max(a, b);
}
Node unite(Node aa, Node bb){
Node res;
res.lazy_x = 0;
res.lazy_both = 0;
res.lef = aa.lef;
res.rig = bb.rig;
for(int st = 0; st < 2; st ++ ){
for(int en = 0; en < 2; en ++ ){
for(int c = 0 ; c < 3; c ++ ){
res.dp[st][en][c] = -(ll)1e18;
}
}
}
int cum;
for(int st = 0 ; st < 2; st ++ ){
for(int en = 0; en < 2; en ++ ){
for(int pi = 0; pi < 3; pi ++ ){
for(int qi = 0; qi < 3; qi ++ ){
cum = min(pi + qi, 2);
upd(res.dp[st][en][cum], aa.dp[st][0][pi] + bb.dp[1][en][qi]);
upd(res.dp[st][en][cum], aa.dp[st][1][pi] + bb.dp[0][en][qi]);
}
upd(res.dp[st][en][pi], aa.dp[st][en][pi]);
upd(res.dp[st][en][pi], bb.dp[st][en][pi]);
}
}
}
return res;
}
Node T[N * 4 + 512];
void push(int node, int cl, int cr){
int bonus;
for(int st = 0; st < 2; st ++ ){
for(int en = 0; en < 2; en ++ ){
for(int cc = 0; cc < 3; cc ++ ){
if(st == en){
bonus = st;
}
else{
bonus = -1;
}
if(bonus != -1){
if(bonus == 0) T[node].dp[st][en][cc] -= T[node].lazy_both;
else T[node].dp[st][en][cc] += T[node].lazy_both;
}
T[node].dp[st][en][cc] += cc * 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].lef = cl;
T[node].rig = cr;
for(int p = 0; p < 2; p ++ ){
for(int q = 0; q < 2; q ++ ){
for(int x = 0 ; x < 3; x ++ ){
T[node].dp[p][q][x] = -(ll)1e18;
}
}
}
if(cl == cr){
T[node].dp[0][0][0] = 0;
T[node].dp[0][1][1] = 0;
T[node].dp[1][1][1] = 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]);
V = max(V, T[1].dp[0][1][2]);
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;
}