Submission #835401

#	Time	Username	Problem	Language	Result	Execution time	Memory
835401		Baytoro	Distributing Candies (IOI21_candies)	C++17	38 / 100	508 ms	34612 KiB

candies

#include "candies.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
const int N=2e5+5;
long long tree[4*N],mn[4*N],mx[4*N],ismn[4*N],ismx[4*N];
void push(int x, int lx, int rx){
	if(lx==rx) return;
	int l=2*x,r=2*x+1;
	mn[l]+=tree[x],mx[l]+=tree[x],tree[l]+=tree[x];
	mn[r]+=tree[x],mx[r]+=tree[x],tree[r]+=tree[x];
	if(ismn[x]){
		mn[l]=min(mn[l],mx[x]);
		mn[r]=min(mn[r],mx[x]);
		mx[l]=min(mx[l],mx[x]);
		mx[r]=min(mx[r],mx[x]);
		ismn[l]=ismn[r]=1;
	}
	if(ismx[x]){
		mn[l]=max(mn[l],mn[x]);
		mn[r]=max(mn[r],mn[x]);
		mx[l]=max(mx[l],mn[x]);
		mx[r]=max(mx[r],mn[x]);
		ismx[l]=ismx[r]=1;
	}
	tree[x]=ismn[x]=ismx[x]=0;
}
void add(int l, int r, int x, int lx, int rx, int v){
	if(l>rx || r<lx) return;
	if(lx<=l && r<=rx){
		mn[x]+=v;
		mx[x]+=v;
		tree[x]+=v;
		return;
	}
	int md=(l+r)/2;
	push(x,l,r);
	add(l,md,2*x,lx,rx,v);
	add(md+1,r,2*x+1,lx,rx,v);
	mn[x]=min(mn[2*x],mn[2*x+1]);
	mx[x]=max(mx[2*x],mx[2*x+1]);
}
void MIN(int l, int r, int x, int lx, int rx, long long v){
	if(l>rx || r<lx) return;
	if(lx<=l && r<=rx){
		mn[x]=min(mn[x],v);
		mx[x]=min(mx[x],v);
		ismn[x]=1;
		return;
	}
	int md=(l+r)/2;
	push(x,l,r);
	MIN(l,md,2*x,lx,rx,v);
	MIN(md+1,r,2*x+1,lx,rx,v);
	mn[x]=min(mn[2*x],mn[2*x+1]);
	mx[x]=max(mx[2*x],mx[2*x+1]);
}
void MAX(int l, int r, int x, int lx, int rx, long long v){
	if(l>rx || r<lx) return;
	if(lx<=l && r<=rx){
		mn[x]=max(mn[x],v);
		mx[x]=max(mx[x],v);
		ismx[x]=1;
		return;
	}
	int md=(l+r)/2;
	push(x,l,r);
	MAX(l,md,2*x,lx,rx,v);
	MAX(md+1,r,2*x+1,lx,rx,v);
	mn[x]=min(mn[2*x],mn[2*x+1]);
	mx[x]=max(mx[2*x],mx[2*x+1]);
}
long long get(int l, int r, int x, int id){
	if(l==r) return mn[x];//<-
	int md=(l+r)/2;
	push(x,l,r);
	if(id<=md) return get(l,md,2*x,id);
	return get(md+1,r,2*x+1,id);
}
vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    int n=c.size(),q=v.size();
    vector<int> a(n);
    bool ok=1;
    for(int i=1;i<n;i++) ok&=(c[i]==c[i-1]);
    if(n<=2000 && q<=2000){
		for(int t=0;t<q;t++){
			for(int i=l[t];i<=r[t];i++){
				a[i]+=v[t];
				a[i]=min(c[i],a[i]);
				a[i]=max(a[i],0);
			}
		}
	}
	else if(ok){
		for(int i=0;i<q;i++){
			add(0,n-1,1,l[i],r[i],v[i]);
			MIN(0,n-1,1,l[i],r[i],c[0]);
			MAX(0,n-1,1,l[i],r[i],0);
		}
		for(int i=0;i<n;i++)
			a[i]=get(0,n-1,1,i);
	}
	else{
		vector<long long> pref(n);
		for(int i=0;i<q;i++){
			pref[l[i]]+=v[i];
			pref[r[i]+1]-=v[i];
		}
		for(int i=1;i<n;i++){
			pref[i]+=pref[i-1];
		}
		for(int i=0;i<n;i++)
			a[i]=min(pref[i],(long long)c[i]);
	}
	return a;
}

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