oj.uz

Submission #625219

# Submission time Handle Problem Language Result Execution time Memory
625219 2022-08-09T16:17:48 Z WongChun1234 Distributing Candies (IOI21_candies) C++17
8 / 100
 331 ms 30004 KB 
#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200050;
struct node{
	ll sum,mn,mx;
}seg[N<<2];
node pushup(node a,node b){
	node ret;
	ret.sum=a.sum+b.sum;
	ret.mn=min(b.mn,a.mn+b.sum);
	ret.mx=max(b.mx,a.mx+b.sum);
	return ret;
}
vector<int> todo[N];
void build(int id,int l,int r){
	if (l==r){
		seg[id].sum=seg[id].mn=seg[id].mx=0;
		return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid); build(id*2+1,mid+1,r);
	seg[id]=pushup(seg[id*2],seg[id*2+1]);
}
void modify(int id,int l,int r,int q,int val){
	if (l>q||r<q) return;
	if (l==r){
		seg[id].sum+=val;
		seg[id].mn=min(0LL,seg[id].sum);
		seg[id].mx=max(0LL,seg[id].sum);
		return;
	}
	int mid=(l+r)/2;
	modify(id*2,l,mid,q,val); modify(id*2+1,mid+1,r,q,val);
	seg[id]=pushup(seg[id*2],seg[id*2+1]);
}
int query(int id,int l,int r,int q,int c,ll cmin,ll cmax,ll curr){
	//if (l>q||r<q) return 0;
	if (l==r){
		//cout<<q<<":"<<l<<"::"<<curr<<","<<cmin<<"-"<<cmax<<"\n";
		int tmax=max(cmax,curr+seg[id].sum),tmin=min(cmin,curr+seg[id].sum);
		//cout<<tmin<<"--"<<tmax<<"\n";
		if (tmax-tmin<=c) return seg[id].sum;
		if (seg[id].sum>0){
			//hit r bound
			return -curr+cmin+c;
		}else{
			//hit l bound
			return -curr;
		}
		//hit l or r
		/*+4 -1 +4
		0 to 7
		return l;*/
	}
	int mid=(l+r)/2;
	if (max(cmax,seg[id*2+1].mx+curr)-min(cmin,seg[id*2+1].mn+curr)<=c){
		return query(id*2,l,mid,q,c,min(cmin,seg[id*2+1].mn+curr),max(cmax,seg[id*2+1].mx+curr),curr+seg[id*2+1].sum)+seg[id*2+1].sum;
	}else{
		return query(id*2+1,mid+1,r,q,c,cmin,cmax,curr);
	}
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n = c.size(), m = l.size();
	vector<int> s(n);
	for (int i=0;i<m;i++){
		todo[l[i]].push_back(i);
		todo[r[i]+1].push_back(i);
	}
	build(1,1,m);
	for (int i=0;i<n;i++){
		for (int j:todo[i]){
			if (l[j]==i){
				//add
				modify(1,1,m,j+1,v[j]);
			}else{
				//remove
				modify(1,1,m,j+1,-v[j]);
			}
		}
		s[i]=query(1,1,m,i+1,c[i],0,0,0);
	}
	return s;
}
/*
3
10 15 13
2
0 2 20
0 1 -11
*/
/*
3
10 15 13
3
0 2 4
1 2 5
0 1 10
*/

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 29860 KB Output is correct
2 Correct 323 ms 30004 KB Output is correct
3 Correct 331 ms 29960 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4952 KB Output is correct
3 Incorrect 98 ms 23752 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -