Submission #1866870
Source Code Expand
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define MAXI 200020
#define u(x, a, b) for(ll x = a; x < b; x++)
#define d(x, a, b) for(ll x = a; x > b; x--)
pair<ll, ll> st0[MAXI][20];// 0 mod 2
pair<ll, ll> st1[MAXI][20];// 1 mod 2
pair<ll, ll> queryst0(ll le, ll ri){
//cerr<<"L R 1 : "<<le<<' '<<ri<<'\n';
int k = log2(ri-le);
ll ans = min(st0[le][k].first, st0[ri-(1 << k)][k].first); // <-- for query [l, r]
ll pos;
if(ans == st0[le][k].first){
pos = st0[le][k].second;
}
else{
//cerr<<"D : "<<ri-(1<<k)<<'\n';
pos = st0[ri-(1 << k)][k].second;
}
pair<ll, ll> t = make_pair(ans, pos);
return t;
}
pair<ll, ll> queryst1(ll le, ll ri){
//cerr<<"L R 1 : "<<le<<' '<<ri<<'\n';
int k = log2(ri-le);
//cerr<<"D : "<<ri-(1<<k)<<'\n';
ll ans = min(st1[le][k].first, st1[ri-(1 << k)][k].first); // <-- for query [l, r]
ll pos;
if(ans == st1[le][k].first){
pos = st1[le][k].second;
}
else{
pos = st1[ri-(1 << k)][k].second;
}
pair<ll, ll> t = make_pair(ans, pos);
return t;
}
deque< pair<ll, ll> > greedy(vector<ll> in, ll le, ll ri){
deque< pair<ll, ll> > ans;
ll min1, tar1, min2, tar2;
if(le >= ri){
ans.push_back(make_pair(MAXI, MAXI));
return ans;
}
if(le%2){
pair<ll, ll> v = queryst1(le, ri);
tar1 = v.second;
min1 = v.first;
}
else{
pair<ll, ll> v = queryst0(le, ri);
tar1 = v.second;
min1 = v.first;
}
if((tar1+1)%2){
pair<ll, ll> v = queryst1(tar1+1, ri);
tar2 = v.second;
min2 = v.first;
}
else{
pair<ll, ll> v = queryst0(tar1+1, ri);
tar2 = v.second;
min2 = v.first;
}
ans.push_back(make_pair(min1, min2));
deque< pair<ll, ll> > a1 = greedy(in, le, tar1), a2 = greedy(in, tar1+1, tar2), a3 = greedy(in, tar2+1, ri);
ll y = MAXI;
if(!a1.empty()){
y = min(a1[0].first, y);
}
if(!a2.empty()){
y = min(a2[0].first, y);
}
if(!a3.empty()){
y = min(a3[0].first, y);
}
while(y < MAXI){
if(!a1.empty()){
if(y == a1[0].first){
ans.push_back(a1[0]);
a1.pop_front();
}
}
if(!a2.empty()){
if(y == a2[0].first){
ans.push_back(a2[0]);
a2.pop_front();
}
}
if(!a3.empty()){
if(y == a3[0].first){
ans.push_back(a3[0]);
a3.pop_front();
}
}
y = MAXI;
if(!a1.empty()){
y = min(a1[0].first, y);
}
if(!a2.empty()){
y = min(a2[0].first, y);
}
if(!a3.empty()){
y = min(a3[0].first, y);
}
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, temp;
cin >> n;
vector<ll> arr;
u(three, 0, n){
cin >> temp;
arr.push_back(temp);
}
//sparse table
int pwr = log2(n);
for(int j = 0;j <= pwr;j++){
for(int i = 0; i < n;i ++){
if(i + (1 << j) - 1 < n){
pair<ll, ll> imax = make_pair(MAXI, i);
pair<ll, ll> curi = make_pair(arr[i], i), cur0, cur1;
if(j){
ll minst0 = min(st0[i][j-1].first, st0[i + (1 << (j-1))][j-1].first), posmin0;
ll minst1 = min(st1[i][j-1].first, st1[i + (1 << (j-1))][j-1].first), posmin1;
if(minst0 == st0[i][j-1].first){
posmin0 = st0[i][j-1].second;
}
else{
posmin0 = st0[i + (1 << (j-1))][j-1].second;
}
if(minst1 == st1[i][j-1].first){
posmin1 = st1[i][j-1].second;
}
else{
posmin1 = st1[i + (1 << (j-1))][j-1].second;
}
cur0 = make_pair(minst0, posmin0);
cur1 = make_pair(minst1, posmin1);
}
st0[i][j] = (j ? cur0 : (i%2==1 ? imax : curi));//if j = 0, i%2 = 0 then st0[i][0] = arr[i]
st1[i][j] = (j ? cur1 : (i%2==1 ? curi : imax));//opposite for st1
}
else{
st0[i][j] = make_pair(MAXI, MAXI);
st1[i][j] = make_pair(MAXI, MAXI);
}
}
}
deque< pair<ll, ll> > fin = greedy(arr, 0, n);
u(three, 0, n/2){
cout << fin[three].first << ' ' << fin[three].second << ' ';
}
}
Submission Info
Submission Time |
|
Task |
E - Young Maids |
User |
vjudge5 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4830 Byte |
Status |
TLE |
Exec Time |
3857 ms |
Memory |
175332 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 |
2560 KB |
0_01.txt |
AC |
2 ms |
2304 KB |
0_02.txt |
AC |
2 ms |
2304 KB |
1_00.txt |
AC |
2 ms |
2304 KB |
1_01.txt |
AC |
2 ms |
2304 KB |
1_02.txt |
TLE |
2320 ms |
-1177776 KB |
1_03.txt |
TLE |
3857 ms |
-593052 KB |
1_04.txt |
TLE |
2325 ms |
-643884 KB |
1_05.txt |
TLE |
2106 ms |
154956 KB |
1_06.txt |
TLE |
2107 ms |
175332 KB |
1_07.txt |
TLE |
2107 ms |
164408 KB |
1_08.txt |
TLE |
2107 ms |
173744 KB |
1_09.txt |
TLE |
2517 ms |
-592308 KB |
1_10.txt |
TLE |
2323 ms |
-634156 KB |
1_11.txt |
TLE |
2298 ms |
-1032620 KB |
1_12.txt |
TLE |
2107 ms |
162340 KB |
1_13.txt |
TLE |
2107 ms |
162692 KB |
1_14.txt |
TLE |
2106 ms |
171508 KB |
1_15.txt |
TLE |
2107 ms |
165596 KB |
1_16.txt |
TLE |
2107 ms |
173232 KB |
1_17.txt |
TLE |
2106 ms |
162752 KB |
1_18.txt |
TLE |
2106 ms |
166912 KB |
1_19.txt |
TLE |
2106 ms |
165324 KB |