Submission #615528

#	Time	Username	Problem	Language	Result	Execution time	Memory
615528		HamletPetrosyan	Distributing Candies (IOI21_candies)	C++17	0 / 100	264 ms	23480 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;

struct node{
	int l, r;
	int lv, mv, rv;
};

int C;
node t[4 * N];

int value(int num, node& a){
	if(num < a.l) return a.lv;
	if(num > a.r) return a.rv;
	return num + a.mv;
}

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

	c.l = max(b.lv - a.mv + 1, a.l);
	c.r = min(b.rv - a.mv - 1, a.r);
}

void build(int v, int tl, int tr){
	if(tl == tr){
		t[v].l = 0, t[v].r = C;
		t[v].lv = t[v].mv; t[v].rv = C;
		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, int val){
	if(tl == tr){
		t[v].l = max(0, 0 - val); t[v].lv = 0;
		t[v].r = min(C, C - val); t[v].rv = C;
		t[v].mv = 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]);

//	cout << tl << " " << tr << ": " << t[v].l << " " << t[v].r << " " << t[v].lv << " " << t[v].mv << " " << t[v].rv << endl;
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    C = c[0];
//	cout << C << endl;
	vector<pii> x;
	vector<int> ret;
	for(int i = 0; i < len(l); i++){
		x.add({l[i], -(i + 1)});
		x.add({r[i], +(i + 1)});
	}
	sort(all(x));
//	for(int i = 0; i < len(x); i++){
//		cout << "(" << x[i].fr << ", " << x[i].sc << ") ";
//	}
//	cout << endl;
	build(1, 1, len(v));
	int ind = 0;
	for(int i = 0; i < len(x); 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 << "------" << 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