| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 708348 | doowey | Ants and Sugar (JOI22_sugar) | C++14 | 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;
};
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 < 3; 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 ++ ){
upd(res.dp[st][en][1], aa.dp[st][0][0] + bb.dp[1][en][1]);
upd(res.dp[st][en][1], aa.dp[st][1][1] + bb.dp[0][en][0]);
upd(res.dp[st][en][0], bb.dp[st][en][0]);
for(int pi = 1; pi < 3; pi ++ ){
for(int qi = 1; qi < 3; qi ++ ){
upd(res.dp[st][en][2], aa.dp[st][0][pi] + bb.dp[1][en][qi]);
upd(res.dp[st][en][2], aa.dp[st][1][pi] + bb.dp[0][en][qi]);
}
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] = D;
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;
}