Submission #434173

#	Time	Username	Problem	Language	Result	Execution time	Memory
434173		vanic	Handcrafted Gift (IOI20_gift)	C++14	100 / 100	579 ms	24932 KiB

gift

#include "gift.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn=5e5+5;
const string s="RB";

const int Log=19, pot=(1<<Log);

int t1[pot*2], t2[pot*2];

void update(int x, int val){
	t1[x]=t2[x]=val;
	for(x/=2; x>0; x/=2){
		t1[x]=max(t1[x*2], t1[x*2+1]);
		t2[x]=min(t2[x*2], t2[x*2+1]);
	}
}

pair < int, int > query(int L, int D, int x, int l, int d){
	if(L>=l && D<=d){
		return {t1[x], t2[x]};
	}
	pair < int, int > lijeva={0, 1}, desna={0, 1};
	if((L+D)/2>=l){
		lijeva=query(L, (L+D)/2, x*2, l, d);
	}
	if((L+D)/2+1<=d){
		desna=query((L+D)/2+1, D, x*2+1, l, d);
	}
	return {max(lijeva.first, desna.first), min(lijeva.second, desna.second)};
}

int poz[maxn];
int neg[maxn];
string sol;

int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
	for(int i=0; i<r; i++){
		if(x[i]==1){
			poz[a[i]]++;
			neg[b[i]+1]++;
		}
	}
	int sw=0;
	bool pp=0;
	for(int i=0; i<n; i++){
		sw-=neg[i];
		if(!sw){
			pp^=1;
		}
		sw+=poz[i];
		update(i+pot, pp);
		sol.push_back(s[pp]);
	}
	pair < int, int > p;
	for(int i=0; i<r; i++){
		if(x[i]==2){
			p=query(0, pot-1, 1, a[i], b[i]);
			if(p.first==p.second){
				return 0;
			}
		}
	}
	craft(sol);
	return 1;
}

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