Submission #1869093
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,p[maxn];
struct SegTree{
int op,pos[maxn<<2];
#define lc (nd<<1)
#define rc (nd<<1|1)
#define mid ((s+t)>>1)
void init(int _op) {op=_op;}
void build(int nd,int s,int t)
{
if (s==t)
{
pos[nd]=(s&1)==op?s:0;
return;
}
build(lc,s,mid);
build(rc,mid+1,t);
pos[nd]=p[pos[lc]]<p[pos[rc]]?pos[lc]:pos[rc];
}
int query(int nd,int s,int t,int l,int r)
{
if (l<=s&&t<=r) return pos[nd];
int Ans=0,tmp;
if (l<=mid) tmp=query(lc,s,mid,l,r),Ans=p[Ans]<p[tmp]?Ans:tmp;
if (r> mid) tmp=query(rc,mid+1,t,l,r),Ans=p[Ans]<p[tmp]?Ans:tmp;
return Ans;
}
#undef lc
#undef rc
#undef mid
}S[2];
struct Interval{
int l,r,u,v;
Interval() {}
Interval(int l,int r):l(l),r(r)
{
u=S[l&1].query(1,1,n,l,r);
v=S[(l&1)^1].query(1,1,n,u+1,r);
}
bool operator < (const Interval &i) const {return p[u]>p[i.u];}
};
priority_queue<Interval> q;
int main()
{
#ifdef h10
freopen("E.in","r",stdin);
freopen("E.out","w",stdout);
#endif
int i;
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&p[i]);
p[0]=0x7fffffff;
S[0].init(0); S[0].build(1,1,n);
S[1].init(1); S[1].build(1,1,n);
q.push(Interval(1,n));
while (!q.empty())
{
Interval t=q.top(); q.pop();
printf("%d %d ",p[t.u],p[t.v]);
if (t.l<t.u-1)
q.push(Interval(t.l,t.u-1));
if (t.u+1<t.v-1)
q.push(Interval(t.u+1,t.v-1));
if (t.v+1<t.r)
q.push(Interval(t.v+1,t.r));
}
}
Submission Info
Submission Time
2017-12-13 18:05:09+0900
Task
E - Young Maids
User
h10
Language
C++14 (GCC 5.4.1)
Score
800
Code Size
1521 Byte
Status
AC
Exec Time
104 ms
Memory
9204 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:61:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:62:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for (i=1;i<=n;i++) scanf("%d",&p[i]);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
800 / 800
Status
Set Name
Test Cases
Sample
0_00.txt, 0_01.txt, 0_02.txt
All
0_00.txt, 0_01.txt, 0_02.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt
Case Name
Status
Exec Time
Memory
0_00.txt
AC
2 ms
2304 KB
0_01.txt
AC
1 ms
2304 KB
0_02.txt
AC
1 ms
2304 KB
1_00.txt
AC
1 ms
2304 KB
1_01.txt
AC
2 ms
2304 KB
1_02.txt
AC
60 ms
8320 KB
1_03.txt
AC
59 ms
8320 KB
1_04.txt
AC
78 ms
8320 KB
1_05.txt
AC
103 ms
9076 KB
1_06.txt
AC
104 ms
8952 KB
1_07.txt
AC
104 ms
9204 KB
1_08.txt
AC
100 ms
8952 KB
1_09.txt
AC
62 ms
8320 KB
1_10.txt
AC
79 ms
8320 KB
1_11.txt
AC
72 ms
8448 KB
1_12.txt
AC
100 ms
8952 KB
1_13.txt
AC
104 ms
8952 KB
1_14.txt
AC
103 ms
8952 KB
1_15.txt
AC
104 ms
8952 KB
1_16.txt
AC
104 ms
8952 KB
1_17.txt
AC
104 ms
8952 KB
1_18.txt
AC
103 ms
8952 KB
1_19.txt
AC
103 ms
8952 KB