This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "gift.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=0;i<(n);++i)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,a,b) for (int i=(a);i>=(b);--i)
#define FORD(i,n) for (int i=(n)-1;i>=0;--i)
#define trav(to,v) for (auto to : v)
#define fr first
#define sc second
#define pir pair<int,int>
#define mpr make_pair
#define all(v) v.begin(),v.end()
#define ad push_back
mt19937 rng(5165);
typedef long long ll;
struct item{
int val,mn,lz,prior,sz;
item *l, *r;
item(){
val=mn=lz=0;
sz=1;
l=r=NULL;
prior=rng();
}
};
typedef struct item * pitem;
const int N=2006;
pitem getitem(){
static item nodes[N];
static int counter=0;
return &nodes[counter++];
}
int size(pitem t){
if (t)return t->sz;
return 0;
}
int mn(pitem t){
if (t)return t->mn;
return 1;
}
void upd(pitem t){
if (!t)return;
t->sz=size(t->l)+size(t->r)+1;
t->mn=(min(mn(t->l),mn(t->r)),t->val);
}
void make(pitem t){
if (t){
t->val=1;
t->mn=1;
t->lz=1;
}
}
void push(pitem t){
if (t && t->lz){
make(t->l);
make(t->r);
t->lz=0;
}
}
void merge(pitem &t,pitem l,pitem r){
if (!l){
t=r;
return;
}
if (!r){
t=l;
return;
}
if (l->prior>r->prior){
push(l);
merge(l->r,l->r,r);
t=l;
}
else{
push(r);
merge(r->l,l,r->l);
t=r;
}
upd(t);
}
void split(pitem t,pitem &l,pitem &r,int key,int cur=0){
if (!t){
l=r=NULL;
return;
}
//cout<<size(t->l)<<" "<<size(t)<<" "<<cur<<" "<<key<<endl;
push(t);
if (key<=cur+size(t->l)){
split(t->l,l,t->l,key,cur);
r=t;
}
else{
split(t->r,t->r,r,key,cur+1+size(t->l));
l=t;
}
upd(t);
}
void pb(pitem &t){
pitem tv=getitem();
merge(t,t,tv);
}
void print(pitem t){
if (!t)return;
push(t);
print(t->l);
cout<<t->val<<" ";
print(t->r);
}
void cutmk(pitem &t,int l,int r){
pitem a1,a2,a3;
//cout<<l<<" "<<r<<endl;
//print(t);
//cout<<endl;
split(t,a2,a3,r+1);
//print(a2);
//cout<<endl;
split(a2,a1,a2,l);
//print(a1);
//cout<<endl;
//print(a2);
//cout<<endl;
//print(a3);
//cout<<endl;
make(a2);
//print(a2);
//cout<<endl;
merge(t,a1,a2);
//print(a3);
//cout<<endl;
merge(t,t,a3);
//print(t);
//cout<<endl;
}
bool check(pitem t,int l,int r){
bool ans=false;
pitem a1,a2,a3;
split(t,a2,a3,r+1);
split(a2,a1,a2,l);
assert(size(a2)==r+1-l);
if (mn(a2)==0)ans=true;
merge(t,a1,a2);
merge(t,t,a3);
return ans;
}
string ans;
void answer(pitem t){
if (!t)return;
push(t);
answer(t->l);
if (t->val==1){
if (ans.back()=='B')ans+='B';
else ans+='R';
}
else{
if (ans.back()=='B')ans+='R';
else ans+='B';
}
// cout<<ans<<endl;
answer(t->r);
}
int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) {
pitem treap=NULL;
FOR(i,n-1){
pb(treap);
}
//print(treap);
//cout<<endl;
FOR(i,r){
if (x[i]==1){
if (a[i]==b[i])continue;
cutmk(treap,a[i],b[i]-1);
//print(treap);
//cout<<endl;
}
}
//print(treap);
//cout<<endl;
FOR(i,r){
if (x[i]==2){
if (a[i]==b[i]){
return 0;
}
if (!check(treap,a[i],b[i]-1)){
return 0;
}
}
}
ans="R";
answer(treap);
craft(ans);
return 1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |