oj.uz

Submission #435493

# Submission time Handle Problem Language Result Execution time Memory
435493 2021-06-23T11:29:05 Z tmp_bad Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 13424 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
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 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 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 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -