Submission #1301714
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
using vi=vector<int>;
#define PB push_back
#define ALL(x) x.begin(),x.end()
//#define LN cerr<<__LINE__<<endl
#define LN 0
using pi=pair<int,int>;
int read(){
int i;
scanf("%d",&i);
return i;
}
void chmin(int&a,int b){
a=a<b?a:b;
}
void chmax(int&a,int b){
a=a>b?a:b;
}
struct SegTree{
vi buf;
int s;
SegTree(int n){
s=1;
while(s<n)s*=2;
buf.resize(s*2,-1);
}
void Update(int i,int v){
i+=s;
buf[i]=v;
while((i/=2)>=1)buf[i]=max(buf[i*2],buf[i*2+1]);
}
int GetIdx(int b,int e,int t,vi&dst,int l,int r,int i){
if(buf[i]<=t||e<=l||r<=b)return t;
if(b<=l&&r<=e){
if(l+1==r){
if(t<buf[i])dst.PB(l);
return max(t,buf[i]);
}else{
if(t<buf[i*2])
t=GetIdx(b,e,t,dst,l,(l+r)/2,i*2);
if(t<buf[i*2+1])
t=GetIdx(b,e,t,dst,(l+r)/2,r,i*2+1);
return t;
}
}
t=GetIdx(b,e,t,dst,l,(l+r)/2,i*2);
t=GetIdx(b,e,t,dst,(l+r)/2,r,i*2+1);
return t;
}
void GetIdx(int b,int e,vi& dst){
GetIdx(b,e,-1,dst,0,s,1);
}
};
inline int xorshift(){
static int w=1145141919;
w=w^(w<<17);
w=w^(w>>13);
w=w^(w<<5);
return w;
}
struct Node{
Node *l,*r;
int v,s;
} buf[200010];
Node* Merge(Node*a,Node*b){
if(!a)return b;
if(!b)return a;
int s=a->s+b->s,x=xorshift()%s;
if(x<a->s){
a->r=Merge(a->r,b);
a->s=s;
return a;
}else{
b->l=Merge(a,b->l);
b->s=s;
return b;
}
}
using pn=pair<Node*,Node*>;
pn Split(Node*x,int t){
if(!x)return pn(0,0);
if(t<=x->v){
pn c=Split(x->l,t);
if(c.first)x->s-=c.first->s;
x->l=c.second;
return pn(c.first,x);
}else{
pn c=Split(x->r,t);
if(c.second)x->s-=c.second->s;
x->r=c.first;
return pn(x,c.second);
}
}
int MaxValue(Node* x){
while(x->r)x=x->r;
return x->v;
}
void Show(Node* x){
if(!x)return;
Show(x->l);
cerr<<x->v<<" ";
Show(x->r);
}
int main(){
int n=read();
SegTree seg(n*2);
vector<Node*> trs(n*2);
vi mx(n*2,-1);
REP(i,n){
int x=read()-1;
seg.Update(i,x);
trs[i]=buf+i;
trs[i]->v=x;
trs[i]->s=1;
mx[i]=x;
}
vi idx;
FOR(i,n,n*2){
idx.clear();
seg.GetIdx(0,i,idx);
int last=-1;
Node*x=0;
for(auto j:idx){
LN;
pn c=Split(trs[j],last);
LN;
last=mx[j];
LN;
if(c.first)
mx[j]=MaxValue(c.first);
else
mx[j]=-1;
LN;
seg.Update(j,mx[j]);
LN;
trs[j]=c.first;
LN;
x=Merge(x,c.second);
LN;
}
if(x->s==n){
cout<<i-n<<endl;
return 0;
}
mx[i]=last;
seg.Update(i,mx[i]);
trs[i]=x;
//Show(x);
}
}
Submission Info
Submission Time
2017-05-21 19:02:39+0900
Task
F - Strange Sorting
User
maroonrk
Language
C++14 (GCC 5.4.1)
Score
2400
Code Size
2692 Byte
Status
AC
Exec Time
1111 ms
Memory
15744 KB
Compile Error
./Main.cpp: In function ‘int read()’:
./Main.cpp:13:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&i);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
2400 / 2400
Status
Set Name
Test Cases
Sample
sample1.txt, sample2.txt, sample3.txt
All
sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name
Status
Exec Time
Memory
in1.txt
AC
1081 ms
13696 KB
in10.txt
AC
1089 ms
13696 KB
in11.txt
AC
1091 ms
15744 KB
in12.txt
AC
1092 ms
13696 KB
in13.txt
AC
1094 ms
13696 KB
in14.txt
AC
1089 ms
13696 KB
in15.txt
AC
1086 ms
13696 KB
in16.txt
AC
1075 ms
13696 KB
in17.txt
AC
1102 ms
15744 KB
in18.txt
AC
1081 ms
13696 KB
in19.txt
AC
1091 ms
13696 KB
in2.txt
AC
1086 ms
13696 KB
in20.txt
AC
1084 ms
13696 KB
in21.txt
AC
73 ms
14840 KB
in22.txt
AC
126 ms
13696 KB
in23.txt
AC
1 ms
256 KB
in3.txt
AC
1099 ms
13696 KB
in4.txt
AC
1092 ms
13696 KB
in5.txt
AC
1111 ms
13696 KB
in6.txt
AC
1088 ms
13696 KB
in7.txt
AC
1099 ms
13696 KB
in8.txt
AC
1081 ms
13696 KB
in9.txt
AC
1095 ms
13696 KB
sample1.txt
AC
1 ms
256 KB
sample2.txt
AC
1 ms
256 KB
sample3.txt
AC
1 ms
256 KB