oj.uz

Submission #835397

# Submission time Handle Problem Language Result Execution time Memory
835397 2023-08-23T14:05:59 Z Baytoro Distributing Candies (IOI21_candies) C++17
11 / 100
 233 ms 13660 KB 
#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],mn[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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 13660 KB Output is correct
2 Correct 82 ms 12892 KB Output is correct
3 Correct 80 ms 12852 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 308 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 83 ms 13660 KB Output is correct
7 Correct 82 ms 12892 KB Output is correct
8 Correct 80 ms 12852 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Incorrect 233 ms 8144 KB Output isn't correct
11 Halted 0 ms 0 KB -