Submission #2092616
Source Code Expand
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#define inf 1000000000
using namespace std;
typedef pair<int, int> P;
struct SegTree{
int size;
vector<P> seg;
SegTree(){}
SegTree(int size){
this->size = size;
seg.resize(1<<(size+1));
}
void init(){
for(int i = 0; i < (1<<(size+1)); i++) seg[i] = make_pair(inf, inf);
}
void update(int i, P val)
{
i += (1 << size);
seg[i] = val;
while(i > 1){
i /= 2;
seg[i] = min(seg[i*2], seg[i*2+1]);
}
}
P query(int a, int b, int k, int l, int r)
{
if(b < l || r < a) return make_pair(inf, inf);
if(a <= l && r <= b) return seg[k];
P lval = query(a, b, k*2, l, (l+r)/2);
P rval = query(a, b, k*2+1, (l+r)/2+1, r);
return min(lval, rval);
}
P query(int a, int b)
{
return query(a, b, 1, 0, (1<<size)-1);
}
};
SegTree odd(17), even(17);
struct Range{
int l, r;
P p1, p2;
Range(){}
Range(int a, int b){
l = a, r = b;
calc();
}
void calc(){
if(l%2){
p1 = odd.query(l, r);
p2 = even.query(p1.second+1, r);
}
else{
p1 = even.query(l, r);
p2 = odd.query(p1.second+1, r);
}
}
bool operator>(const Range& obj)const{
return p1 > obj.p1;
}
};
int N;
priority_queue< Range, vector<Range>, greater<Range> > Q;
vector<int> ans;
int main(void)
{
odd.init(), even.init();
cin >> N;
int p;
for(int i = 1; i <= N; i++){
cin >> p;
if(i%2) odd.update(i, make_pair(p, i));
else even.update(i, make_pair(p, i));
}
Range rg;
Q.push(Range(1, N));
while(Q.size()){
rg = Q.top(), Q.pop();
ans.push_back(rg.p1.first);
ans.push_back(rg.p2.first);
if(rg.p1.second != rg.l) Q.push(Range(rg.l, rg.p1.second-1));
if(rg.p2.second != rg.r) Q.push(Range(rg.p2.second+1, rg.r));
if(rg.p1.second+1 != rg.p2.second) Q.push(Range(rg.p1.second+1, rg.p2.second-1));
}
for(int i = 0; i < ans.size(); i++){
cout << ans[i];
if(i != ans.size()-1) cout << " ";
}
cout << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Young Maids |
User |
leaf1415 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2054 Byte |
Status |
RE |
Exec Time |
150 ms |
Memory |
4352 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
4 ms |
4352 KB |
0_01.txt |
AC |
4 ms |
4352 KB |
0_02.txt |
AC |
4 ms |
4352 KB |
1_00.txt |
AC |
4 ms |
4352 KB |
1_01.txt |
AC |
4 ms |
4352 KB |
1_02.txt |
RE |
141 ms |
4352 KB |
1_03.txt |
RE |
150 ms |
4352 KB |
1_04.txt |
RE |
144 ms |
4352 KB |
1_05.txt |
RE |
143 ms |
4352 KB |
1_06.txt |
RE |
143 ms |
4352 KB |
1_07.txt |
RE |
144 ms |
4352 KB |
1_08.txt |
RE |
144 ms |
4352 KB |
1_09.txt |
RE |
148 ms |
4352 KB |
1_10.txt |
RE |
146 ms |
4352 KB |
1_11.txt |
RE |
143 ms |
4352 KB |
1_12.txt |
RE |
146 ms |
4352 KB |
1_13.txt |
RE |
145 ms |
4352 KB |
1_14.txt |
RE |
145 ms |
4352 KB |
1_15.txt |
RE |
145 ms |
4352 KB |
1_16.txt |
RE |
145 ms |
4352 KB |
1_17.txt |
RE |
146 ms |
4352 KB |
1_18.txt |
RE |
145 ms |
4352 KB |
1_19.txt |
RE |
145 ms |
4352 KB |