Submission #394156

#	Time	Username	Problem	Language	Result	Execution time	Memory
394156		jairRS	Handcrafted Gift (IOI20_gift)	C++17	0 / 100	1 ms	428 KiB

gift

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

int construct(int n, int r, vector<int> a, vector<int> b,  vector<int> x);
void craft(std::string &s);

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;
}

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(pos){
		string ans;
		for (int i = 1; i <= n; i++)
		{
			ans.pb(segTree[i + treeSize/2] == 1 ? 'R' : 'B');
			craft(ans);
			cerr << ans << '\n';
		}
		return 1;
	}
	return 0;
}

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