oj.uz

Submission #1025024

# Submission time Handle Problem Language Result Execution time Memory
1025024 2024-07-16T14:21:54 Z Unforgettablepl Ants and Sugar (JOI22_sugar) C++17
16 / 100
 2069 ms 333392 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 164452 KB Output is correct
2 Correct 149 ms 164508 KB Output is correct
3 Incorrect 152 ms 164432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 164436 KB Output is correct
2 Correct 141 ms 164432 KB Output is correct
3 Correct 138 ms 164480 KB Output is correct
4 Correct 1424 ms 181936 KB Output is correct
5 Correct 509 ms 176208 KB Output is correct
6 Correct 1664 ms 184912 KB Output is correct
7 Correct 515 ms 176284 KB Output is correct
8 Correct 2017 ms 188756 KB Output is correct
9 Correct 1012 ms 189264 KB Output is correct
10 Correct 2069 ms 188664 KB Output is correct
11 Correct 914 ms 189264 KB Output is correct
12 Correct 497 ms 173908 KB Output is correct
13 Correct 657 ms 177484 KB Output is correct
14 Correct 984 ms 186092 KB Output is correct
15 Correct 995 ms 185912 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 223 ms 333392 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 164452 KB Output is correct
2 Correct 149 ms 164508 KB Output is correct
3 Incorrect 152 ms 164432 KB Output isn't correct
4 Halted 0 ms 0 KB -