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 <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e15;
void strat1(int q){
int l;
cin >> l;
vector<tuple<int,bool,int>> elements; // Sugar is false
auto solve = [&](){
int ans = 0;
queue<pair<int,int>> sugars;
sort(elements.begin(),elements.end());
for(auto[idx,type,amt]:elements){
if(type==false){sugars.emplace(idx,amt);continue;}
while(!sugars.empty() and sugars.front().first<idx-2*l)sugars.pop();
while(!sugars.empty()){
if(amt>=sugars.front().second){
amt-=sugars.front().second;
ans+=sugars.front().second;
sugars.pop();
} else {
ans+=amt;
sugars.front().second-=amt;
break;
}
}
}
return ans;
};
for(int i=1;i<=q;i++){
int type,x,a;cin>>type>>x>>a;
if(type==1){
elements.emplace_back(x+l,true,a);
} else {
elements.emplace_back(x,false,a);
}
cout << solve() << '\n';
}
exit(0);
}
struct node{
vector<vector<int>> DP;
int sugar;
node(int sugar=0,int ants=0):DP(2,vector<int>(2)),sugar(sugar){
DP[0][1]=DP[1][0]=-INF;
DP[1][1]=ants-sugar;
}
node(const node &a,const node &b):DP(2,vector<int>(2)),sugar(b.sugar){
for(int x=0;x<2;x++){
for(int y=0;y<2;y++){
DP[x][y]=max({a.DP[x][0]+b.DP[0][y],a.DP[x][1]+b.DP[1][y],a.DP[x][1]+b.DP[0][y],a.DP[x][0]+b.DP[1][y]-a.sugar});
}
}
}
};
struct segtree{
vector<node> tree;
segtree():tree(1048576){}
void update(int k,int s,int a){
k+=524288;
tree[k]={s,a};
while(k/=2){
tree[k]={tree[2*k],tree[2*k+1]};
}
}
};
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
if(q<=3000)strat1(q);
vector<int> sugars(q+1);
vector<int> ants(q+1);
int antssum = 0;
int l;cin>>l;
segtree seg;
for(int i=1;i<=q;i++){
int t,x,a;cin>>t>>x>>a;x=(x+1ll)/2ll;
if(t==1){ants[x]+=a;antssum+=a;}
else sugars[x]+=a;
seg.update(x,sugars[x],ants[x]);
cout << antssum-max({seg.tree[1].DP[0][0],seg.tree[1].DP[0][1],seg.tree[1].DP[1][0],seg.tree[1].DP[1][1]}) << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |