oj.uz

Submission #835401

# Submission time Handle Problem Language Result Execution time Memory
835401 2023-08-23T14:07:38 Z Baytoro Distributing Candies (IOI21_candies) C++17
38 / 100
 508 ms 34612 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],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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 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 368 KB Output is correct
5 Correct 2 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 8828 KB Output is correct
2 Correct 76 ms 8816 KB Output is correct
3 Correct 75 ms 8812 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 222 ms 5224 KB Output is correct
3 Correct 84 ms 26552 KB Output is correct
4 Correct 495 ms 33840 KB Output is correct
5 Correct 508 ms 34228 KB Output is correct
6 Correct 490 ms 34612 KB Output is correct
7 Correct 501 ms 33996 KB Output is correct

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 44 ms 4964 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 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 368 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 83 ms 8828 KB Output is correct
7 Correct 76 ms 8816 KB Output is correct
8 Correct 75 ms 8812 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 222 ms 5224 KB Output is correct
11 Correct 84 ms 26552 KB Output is correct
12 Correct 495 ms 33840 KB Output is correct
13 Correct 508 ms 34228 KB Output is correct
14 Correct 490 ms 34612 KB Output is correct
15 Correct 501 ms 33996 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Incorrect 44 ms 4964 KB Output isn't correct
19 Halted 0 ms 0 KB -