Submission #615752

#	Time	Username	Problem	Language	Result	Execution time	Memory
615752		HamletPetrosyan	Distributing Candies (IOI21_candies)	C++17	0 / 100	329 ms	32052 KiB

candies

#include "candies.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define ll long long
#define add push_back
#define pii pair<int, int>
#define len(a) ((int)(a).size())
#define all(a) a.begin(), a.end()

#define fr first
#define sc second

const int N = 3e5 + 5;

ll C;

struct node {
	ll l, r;
	ll lv, mv, rv;

	void setvalue(ll val){
		l = max(0ll, 0ll - val);
		r = min(C, C - val);
		lv = 0ll;
		rv = C;
		mv = val;
	}
};

ll value(ll num, node& n){
	if(n.l <= num && num <= n.r){
		return num + n.mv;
	}
	if(n.r < 0) return n.rv;
	if(n.l > C) return n.lv;

	if(num < n.l) return n.lv;
	return n.rv;
}

void merge(node& c, node& a, node& b){
	c.mv = a.mv + b.mv;
	c.lv = b.lv;
	c.rv = b.rv;

	if(a.lv >= b.l) {
		c.l = a.l;
		c.lv = value(a.lv, b);
	}
	else if(a.rv < b.l) c.l = C + 1;
	else c.l = max(a.l, b.l - a.mv);
	c.l = max(c.l, 0 - c.mv);

	if(a.rv <= b.r){
	   	c.r = a.r;
		c.rv = value(a.rv, b);
	}
	else if(a.lv > b.r) c.r = 0;
	else c.r = min(a.r, b.r - a.mv);
	c.r = min(c.r, C - c.mv);
}

node t[4 * N];

void build(int v, int tl, int tr){
	if(tl == tr){
		t[v].l = 0; t[v].r = C;
		t[v].lv = 0; t[v].rv = C;
		t[v].mv = 0;
		return;
	}
	int tm = (tl + tr) / 2;
	build(2 * v, tl, tm);
	build(2 * v + 1, tm + 1, tr);
	merge(t[v], t[2 * v], t[2 * v + 1]);
}

void update(int v, int tl, int tr, int ind, ll val){
	if(tl == tr){
		t[v].setvalue(val);
		return;
	}
	int tm = (tl + tr) / 2;
	if(ind <= tm) update(2 * v, tl, tm, ind, val);
	else update(2 * v + 1, tm + 1, tr, ind, val);
	merge(t[v], t[2 * v], t[2 * v + 1]);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	C = c[0];

	vector<pii> x;
	vector<int> ret;
	for(int i = 0; i < len(v); i++){
		x.add({l[i], -(i + 1)});
		x.add({r[i], +(i + 1)});
	}
	sort(all(x));

	build(1, 1, len(v));
	int ind = 0;
	for(int i = 0; i < len(c); i++){
		while(ind < len(x) && x[ind].fr == i && x[ind].sc < 0){
			update(1, 1, len(v), -x[ind].sc, v[-x[ind].sc - 1]);
			ind++;
		}
		ret.add(value(0, t[1]));

//		cout << t[1].l << " " << t[1].r << " | " << t[1].lv << " " << t[1].mv << " " << t[1].rv << endl;
		while(ind < len(x) && x[ind].fr == i && x[ind].sc > 0){
			update(1, 1, len(v), x[ind].sc, 0);
			ind++;
		}
	}
	return ret;
}

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