Submission #394201

#	Time	Username	Problem	Language	Result	Execution time	Memory
394201		jairRS	Handcrafted Gift (IOI20_gift)	C++17	35 / 100	515 ms	27220 KiB

gift

#include "gift.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef vector<int> vi;

struct q{
	int l, r, type;
	q(int a = 0, int b = 0, int c = 0){
		l = a; r = b; type = c;
	}
};

const bool customSort(q & a, q & b){
	return a.type < b.type;
}

void update(int i, int ql, int qr, int l, int r, vi & tree, vi & lazy){
	if(l >= ql && r <= qr){
		tree[i] = r - l + 1;
		if(l == r) return;
		lazy[i*2] = 1;
		lazy[i*2 + 1] = 1;
		return;
	}
	if(l > qr || r < ql) return;

	update(i*2, ql, qr, l, (l + r)/2, tree, lazy);
	update(i*2 + 1, ql, qr, (l + r)/2 + 1, r, tree, lazy);
}

int query(int i, int ql, int qr, int l, int r, vi & tree, vi & lazy){
	if(lazy[i]){
		lazy[i] = 0;
		tree[i] = r - l + 1;
		if(l != r){
			lazy[i*2] = 1;
			lazy[i*2 + 1] = 1;
		}
	}
	if(l >= ql && r <= qr) return tree[i];
	if(l > qr || r < ql) return 0;

	int q1 = query(i*2, ql, qr, l, (l + r)/2, tree, lazy);
	int q2 = query(i*2 + 1, ql, qr, (l + r)/2 + 1, r, tree, lazy);
	return q1 + q2;
}

void finish(int i, int l, int r, vi & tree){
	if(l == r) return;
	if(tree[i]){
		int toRem = min(tree[i], (r - l + 1)/2);
        tree[i] -= toRem;
        tree[i*2] = max(toRem, tree[i*2]);
        tree[i*2 + 1] = max(tree[i*2 + 1], tree[i]);
	}

	finish(i*2, l, (l + r)/2, tree);
	finish(i*2 + 1, (l + r)/2 + 1, r, tree);
}

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
	vector<q> queries(r);
	for (int i = 0; i < r; i++)
	{
		queries[i] = q(a[i] + 1, b[i] + 1, x[i]);
	}
	sort(queries.begin(), queries.end(), customSort);

	int power2 = 1;
	while(power2 < n) power2 *= 2;
	int treeSize = 2*power2 - 1;
	vi segTree(treeSize + 1, 0);
	vi lazy(treeSize + 1, 0);

	bool pos = true;
	for (int i = 0; i < r; i++)
	{
		q cur = queries[i];
		if(cur.type == 1){
			update(1, cur.l, cur.r, 1, power2, segTree, lazy);
		} else {
			int sum = query(1, cur.l, cur.r, 1, power2, segTree, lazy);
			if(sum == cur.r - cur.l + 1) pos = false;
			if(cur.r == cur.l) pos = false;
			if(sum == 0) segTree[(cur.r + cur.l)/2 + treeSize/2] = 1;
		}
	}
	finish(1, 1, power2, segTree);

	if(pos){
		string ans;
		for (int i = 1; i <= n; i++)
		{
			ans.pb((segTree[i + treeSize/2] == 1 ? 'R' : 'B'));
		}
        craft(ans);
		return 1;
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 25 / 25
• Subtask 5: 0 / 30