#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
random_device rnd;
mt19937 rd(random_device{}());
struct node
{
int v, w, sz, sum;
node *l, *r;
bool rev;
node(int v_ = 0)
{
v = sum = v_;
w = rd();
sz = 1;
l = r = nullptr;
rev = false;
}
};
inline int sz(node *t)
{
return t ? t->sz : 0;
}
inline int sum(node *t)
{
return t ? t->sum : 0;
}
inline void flush(node *t)
{
if(!t || !t->rev) return;
swap(t->l, t->r);
if(t->l) t->l->rev ^= 1;
if(t->r) t->r->rev ^= 1;
}
inline void update(node *t)
{
if(t == nullptr) return;
t->sz = sz(t->l) + sz(t->r) + 1;
t->sum = sum(t->l) + sum(t->r) + t->v;
}
inline void merge(node*& t, node *l, node *r)
{
if(!l || !r) return void(t = l?l:r);
flush(l), flush(r);
if(l->w >= r->w)
{
merge(l->r, l->r, r);
t = l;
}
else
{
merge(r->l, l, r->l);
t = r;
}
update(t);
}
inline void split(node *t, node*& l, node*& r, int p)
{
if(!t) return void(l = r = nullptr);
flush(t);
int pos = sz(t->l) + 1;
if(pos < p)
{
l = t;
split(t->r, t->r, r, p-pos);
}
else
{
r = t;
split(t->l, l, t->l, p);
}
update(t);
}
inline void insert(node*& t, int p, int v)
{
node *l = 0, *r = 0, *aux = new node((v == p));
split(t, l, r, p);
merge(l, l, aux);
merge(t, l, r);
}
inline void reverse(node*& t, int l, int r)
{
node *a = 0, *b = 0, *aux = 0;
split(t, a, b, r+1);
split(a, aux, a, l);
a->rev ^= 1;
merge(a, aux, a);
merge(t, a, b);
}
ostream& operator<<(ostream& out, node *t)
{
flush(t);
if(t) out << t->l << t->v << " " << t->r;
return out;
}
int v[maxn], pfsum[maxn] , n;
int pos[maxn];
int main()
{
node *t=0;
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
int x;
cin >> x;
v[i] = x;
insert(t, i, x);
pos[v[i]] = i;
if(v[i] == i) pfsum[i] = pfsum[i - 1] + 1;
}
vector<pair<int, int>> p;
for(int i = 1; i <= n; i++)
{
if(v[i] == i) continue;
int ini = v[i], fim = pos[v[i]];
if(ini > fim) swap(ini, fim);
p.push_back({ini, fim});
}
int best = 0;
pair<int, int> bp;
for(auto u : p)
{
int ans = 0;
int i = u.first, j = u.second;
ans += pfsum[i - 1];
ans += pfsum[n] - pfsum[j];
int mid = (u.second - u.first)/2;
reverse(t, u.first, u.second);
for(int z = u.first; z <= u.second; z++)
{
if(v[z] == z) ans++;
}
if(ans >= best)
{
best = ans;
bp.first = v[u.first], bp.second = v[u.second];
}
}
//cout << best << "\n";
if(bp.first == 0 and bp.second == 0)
{
for(int i = 1; i <= n; i++)
{
if(v[i] == i) cout << i << " " << i << "\n";
return 0;
}
}
cout << bp.first << " " << bp.second << "\n";
}
Compilation message
doktor.cpp: In function 'int main()':
doktor.cpp:151:7: warning: unused variable 'mid' [-Wunused-variable]
int mid = (u.second - u.first)/2;
^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
508 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
18 ms |
824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
24 ms |
900 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
900 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
58 ms |
1300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1088 ms |
6540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1088 ms |
31656 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1077 ms |
31656 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
