oj.uz

Submission #435810

# Submission time Handle Problem Language Result Execution time Memory
435810 2021-06-23T18:21:47 Z tmp_bad Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 13508 KB 
#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
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 34 ms 332 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5050 ms 13420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 157 ms 4968 KB Output is correct
3 Correct 139 ms 9996 KB Output is correct
4 Correct 1063 ms 13508 KB Output is correct
5 Correct 2627 ms 13504 KB Output is correct
6 Execution timed out 5062 ms 13416 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Execution timed out 5054 ms 4952 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 34 ms 332 KB Output is correct
6 Execution timed out 5050 ms 13420 KB Time limit exceeded
7 Halted 0 ms 0 KB -