Submission #1025024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025024		Unforgettablepl	Ants and Sugar (JOI22_sugar)	C++17	16 / 100	2069 ms	333392 KiB

sugar

#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';
	}
}

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