이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "gift.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Range{
int ls,rs,self;
}one[500005],two[500005];
int cn[2]={0,0};
bool cmp(Range a,Range b){
return a.ls==b.ls?a.rs<b.rs:a.ls<b.ls;
}
bool tag[2000005];
bool check(int ls,int rs,int ld,int rd,int now){
//cout<<ls<<","<<rs<<":"<<ld<<","<<rd<<"-->"<<now<<endl;
if(ls<=ld && rd<=rs)return tag[now];
int mid=(ld+rd)/2;
if(mid>=ls && !check(ls,rs,ld,mid,now<<1))return false;
if(mid+1<=rs && !check(ls,rs,mid+1,rd,now<<1|1))return false;
return true;
}
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){
one[cn[0]].ls=a[i];
one[cn[0]].rs=b[i];
cn[0]++;
}
else{
two[cn[1]].ls=a[i];
two[cn[1]].rs=b[i];
cn[1]++;
}
}
sort(one,one+cn[0],cmp);
for(int i=0;i<cn[0];i++)one[i].self=i;
for(int i=1;i<cn[0];i++){
int now=one[i].self,last=one[i-1].self;
if(one[last].rs>=one[now].ls){
one[last].ls=min(one[last].ls,one[now].ls);
one[last].rs=max(one[last].rs,one[now].rs);
one[now].self=last;
}
}
//for(int i=0;i<cn[0];i++)cout<<one[i].self<<":"<<one[one[i].self].ls<<","<<one[one[i].self].rs<<" ";cout<<endl;
int stn=1;
while(stn<n)stn*=2;//cout<<stn<<endl;
for(int i=0;i<stn+n;i++)tag[i]=false;
for(int i=0;i<cn[0];i++){
if(i==one[i].self){
for(int j=one[i].ls+stn;j<=one[i].rs+stn;j++){
tag[j]=true;
}
}
}
//for(int i=1;i<stn+n;i++)cout<<tag[i]<<" ";cout<<endl;
for(int i=stn-1;i>=1;i--){
if((i<<1)<stn+n){
if((i<<1|1)<stn+n){
tag[i]=tag[i<<1]&&tag[i<<1|1];
}
else{
tag[i]=tag[i<<1];
}
}
}
//for(int i=1;i<stn+n;i++)cout<<tag[i]<<" ";cout<<endl;
string ans="";char ch[2]={'R','B'};int temp=0;
for(int i=stn;i<stn+n;i++){
if(tag[i]==0 || (i>stn && tag[i]==1 && tag[i-1]==0))temp^=1;
ans+=ch[temp];
}//cout<<ans<<endl;
for(int i=0;i<cn[1];i++){
if(check(two[i].ls,two[i].rs,0,stn-1,1))return 0;
}
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... |