Submission #2098801
Source Code Expand
import java.io.*;
import java.util.*;
import java.math.*;
// import java.awt.Point;
public class Main {
InputStream is;
PrintWriter out;
String INPUT = "";
int mod = 1_000_000_007;
int inf = Integer.MAX_VALUE;
void solve(){
int n = ni();
int[] p = new int[n];
for(int i = 0; i < n; i++){
p[i] = ni();
}
SegmentTree even = new SegmentTree(n);
SegmentTree odd = new SegmentTree(n);
for(int i = 0; i < n; i++){
if(i%2==0) even.update(i, p[i], i);
if(i%2==1) odd.update(i, p[i], i);
}
PriorityQueue<Pair> pq = new PriorityQueue<>(1, (a,b) -> Integer.compare(a.q[0],b.q[0]));
int left = 0;
int right = n;
int[] q = even.query(left,right);
pq.add(new Pair(left, right, q));
ArrayList<Integer> ans = new ArrayList<>();
while(!pq.isEmpty()){
Pair tmp = pq.poll();
if(tmp.l%2==0){
ans.add(tmp.q[0]);
q = odd.query(tmp.q[1]+1, tmp.r);
ans.add(q[0]);
if(tmp.l<tmp.q[1]) pq.add(new Pair(tmp.l, tmp.q[1], even.query(tmp.l, tmp.q[1])));
if(tmp.q[1]+1 < q[1]) pq.add(new Pair(tmp.q[1]+1, q[1], odd.query(tmp.q[1]+1, q[1])));
if(q[1]+1<tmp.r) pq.add(new Pair(q[1]+1, tmp.r, even.query(q[1]+1, tmp.r)));
}
if(tmp.l%2==1){
ans.add(tmp.q[0]);
q = even.query(tmp.q[1]+1, tmp.r);
ans.add(q[0]);
if(tmp.l<tmp.q[1]) pq.add(new Pair(tmp.l, tmp.q[1], odd.query(tmp.l, tmp.q[1])));
if(tmp.q[1]+1 < q[1]) pq.add(new Pair(tmp.q[1]+1, q[1], even.query(tmp.q[1]+1, q[1])));
if(q[1]+1<tmp.r) pq.add(new Pair(q[1]+1, tmp.r, odd.query(q[1]+1, tmp.r)));
}
}
for(int i : ans){
out.print(i+" ");
}
out.println();
}
class Pair{
int l;
int r;
int[] q;
Pair(int left, int right, int[] q){
this.l = left;
this.r = right;
this.q = q;
}
}
class SegmentTree {
int n;
int[][] seg;
SegmentTree(int n) {
this.n = Integer.highestOneBit(n) << 1;
this.seg = new int[this.n<<1][2];
for(int i=0;i<(this.n<<1);++i){
seg[i][0] = inf;
seg[i][1] = -1;
}
}
int[] comb(int[] ans1, int[] ans2){
if(ans1[0]<=ans2[0]){
return new int[]{ans1[0], ans1[1]};
}
return new int[]{ans2[0], ans2[1]};
}
void update(int x, int value, int id) {
x += n - 1;
this.seg[x][0] = value;
this.seg[x][1] = id;
while (x > 0) {
x = (x - 1) / 2;
this.seg[x] = comb(this.seg[2 * x + 1], this.seg[2 * x + 2]);
}
}
int[] query(int a,int b,int l,int r,int k){
if(a<=l&&r<=b) return seg[k];
if(b<=l||r<=a) return new int[]{inf, -1};
int[] ans1=query(a,b,l,(l+r)/2,2*k+1);
int[] ans2=query(a,b,(l+r)/2,r,2*k+2);
return comb(ans1, ans2);
}
int[] query(int l, int r) {
return query(l,r,0,n,0);
}
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new Main().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b) && b != ' ')){
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Submission Info
Submission Time |
|
Task |
E - Young Maids |
User |
yuya178 |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
800 |
Code Size |
6648 Byte |
Status |
AC |
Exec Time |
879 ms |
Memory |
163360 KB |
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 |
147 ms |
25544 KB |
0_01.txt |
AC |
150 ms |
24788 KB |
0_02.txt |
AC |
156 ms |
26324 KB |
1_00.txt |
AC |
157 ms |
24660 KB |
1_01.txt |
AC |
151 ms |
26452 KB |
1_02.txt |
AC |
774 ms |
157652 KB |
1_03.txt |
AC |
748 ms |
141860 KB |
1_04.txt |
AC |
818 ms |
159464 KB |
1_05.txt |
AC |
877 ms |
149208 KB |
1_06.txt |
AC |
872 ms |
146328 KB |
1_07.txt |
AC |
862 ms |
148644 KB |
1_08.txt |
AC |
852 ms |
147400 KB |
1_09.txt |
AC |
801 ms |
148344 KB |
1_10.txt |
AC |
831 ms |
159548 KB |
1_11.txt |
AC |
851 ms |
163360 KB |
1_12.txt |
AC |
851 ms |
150752 KB |
1_13.txt |
AC |
874 ms |
149904 KB |
1_14.txt |
AC |
861 ms |
149532 KB |
1_15.txt |
AC |
869 ms |
151252 KB |
1_16.txt |
AC |
858 ms |
151956 KB |
1_17.txt |
AC |
879 ms |
153308 KB |
1_18.txt |
AC |
816 ms |
156852 KB |
1_19.txt |
AC |
871 ms |
151260 KB |