Submission #617470

#	Time	Username	Problem	Language	Result	Execution time	Memory
617470		amunduzbaev	Distributing Candies (IOI21_candies)	C++17	0 / 100	555 ms	28824 KiB

candies

#include "candies.h"

#include "bits/stdc++.h"
using namespace std;

#ifndef EVAL
#include "grader.cpp"
#endif

typedef long long ll;

const ll inf = 1e18;
const int N = 2e5 + 5;

struct ST{
	ll mn[N << 2], mx[N << 2]; //, mn2[N << 2], mx2[N << 2];
	ll p[N << 2], umn[N << 2], umx[N << 2];
	
	void push(int x, int lx, int rx){
		if(lx == rx) return;
		mn[x << 1] += p[x], mx[x << 1] += p[x], p[x << 1] += p[x];
		mn[x << 1 | 1] += p[x], mx[x << 1 | 1] += p[x], p[x << 1 | 1] += p[x];
		
		if(umn[x]){
			mn[x << 1] = min(mn[x << 1], mx[x]);
			mn[x << 1 | 1] = min(mn[x << 1 | 1], mx[x]);
			mx[x << 1] = min(mx[x << 1], mx[x]);
			mx[x << 1 | 1] = min(mx[x << 1 | 1], mx[x]);
		}
		
		if(umx[x]){
			mn[x << 1] = max(mn[x << 1], mn[x]);
			mn[x << 1 | 1] = max(mn[x << 1 | 1], mn[x]);
			mx[x << 1] = max(mx[x << 1], mn[x]);
			mx[x << 1 | 1] = max(mx[x << 1 | 1], mn[x]);
		}
		
		p[x] = umn[x] = umx[x] = 0;
	}
	
	void add(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			mn[x] += v, mx[x] += v; // , mn2[x] += v, mx2[x] += v;
			p[x] += v;
			return;
		} int m = (lx + rx) >> 1;
		push(x, lx, rx);
		add(l, r, v, lx, m, x << 1);
		add(l, r, v, m + 1, rx, x << 1 | 1);
		mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
		mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
	}
	
	void umin(int l, int r, ll v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			mn[x] = min(mn[x], v);
			mx[x] = min(mx[x], v);
			umn[x] = 1;
			return;
		} int m = (lx + rx) >> 1;
		umin(l, r, v, lx, m, x << 1);
		umin(l, r, v, m + 1, rx, x << 1 | 1);
		mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
		mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
	}
	
	void umax(int l, int r, ll v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){
			mn[x] = max(mn[x], v);
			mx[x] = max(mx[x], v);
			umx[x] = 1;
			return;
		} int m = (lx + rx) >> 1;
		umax(l, r, v, lx, m, x << 1);
		umax(l, r, v, m + 1, rx, x << 1 | 1);
		mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
		mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
	}
	
	ll get(int i, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) return mx[x];
		int m = (lx + rx) >> 1;
		if(i <= m) return get(i, lx, m, x << 1);
		else return get(i, m + 1, rx, x << 1 | 1);
	}
}tree;

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	int n = c.size();
	int q = l.size();
	
	for(int i=0;i<q;i++){
		tree.add(l[i], r[i], v[i]);
		tree.umin(l[i], r[i], c[0]);
		tree.umax(l[i], r[i], 0);
	}
	
	vector<int> a(n);
	for(int i=0;i<n;i++){
		a[i] = tree.get(i);
	}
	
	return a;
}

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