Submission #435493

#	Time	Username	Problem	Language	Result	Execution time	Memory
435493		tmp_bad	Distributing Candies (IOI21_candies)	C++17	0 / 100	5025 ms	13424 KiB

candies

#include "candies.h"
#include "bits/stdc++.h"
#define MAXN 200009
using namespace std;
 
typedef long long ll;
typedef pair<int,int> PII;

struct node{
	int a,b,lazy;
}s[MAXN<<2];
void upd(int nd,int v){
	s[nd].a-=v;
	s[nd].b+=v;
	s[nd].lazy+=v;
}
void shift(int nd){
	int &ret=s[nd].lazy;
	upd(nd<<1,ret);
	upd(nd<<1|1,ret);
	ret=0;
}
void inc(int l,int r,int v,int nd,int x,int y){
	if(l>y or x>r)
		return;
	if(l<=x and y<=r and ((v>0 and s[nd].a>=v) or (v<0 and s[nd].b>=-v))){
		upd(nd,v);
		return;
	}
	if(x==y){
		if(v>0){
			s[nd].lazy+=s[nd].a;
			s[nd].b+=s[nd].a;
			s[nd].a=0;
		}
		else{
			s[nd].lazy-=s[nd].b;
			s[nd].a-=s[nd].b;
			s[nd].b=0;
		}
		return;
	}
	shift(nd);
	int mid=(x+y)>>1;
	inc(l,r,v,nd<<1,x,mid);
	inc(l,r,v,nd<<1|1,mid+1,y);
	s[nd].a=min(s[nd<<1].a,s[nd<<1|1].a);
	s[nd].b=min(s[nd<<1].b,s[nd<<1|1].b);
}
void build(int nd,int x,int y,vector<int>&c){
	s[nd].b=s[nd].lazy=0;
	if(x==y){
		s[nd].a=c[x-1];
		return;
	}
	int mid=(x+y)>>1;
	build(nd<<1,x,mid,c);
	build(nd<<1|1,mid+1,y,c);
	s[nd].a=min(s[nd<<1].a,s[nd<<1|1].a);
}
void get(int nd,int x,int y,vector<int>&res){
	if(x==y){
		res[x-1]=s[nd].lazy;
		return;
	}
	shift(nd);
	int mid=(x+y)>>1;
	get(nd<<1,x,mid,res);
	get(nd<<1|1,mid+1,y,res);
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
    int q = l.size();
    build(1,1,n,c);
    vector<int> res(n);
    for(int i=0;i<q;i++)
		inc(l[i]+1,r[i]+1,v[i],1,1,n);
	get(1,1,n,res);
    return res;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33