#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out(){cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cerr << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 1e6 + 10;
int n, a[maxn], L[maxn], R[maxn];
bool vis[maxn];
ll solve(int l, int r, int tl, int tr){
int ql = min(l, L[l]);
int qr = min(r, R[r]);
while(ql < l || qr > r){
while(ql < l){
l--;
ql = min(ql, L[l]);
qr = max(qr, R[l]);
}
while(qr > r){
r++;
ql = min(ql, L[r]);
qr = max(qr, R[r]);
}
}
//debug(l, r);
ll ans = 0;
while(l != tl || r != tr){
int cntl = 0;
bool markl = false;
int idkl = l, idkr = r;
int ql = l, qr = r;
while(idkl > tl && qr == r){
idkl--;
cntl++;
ql = min(ql, L[idkl]);
qr = max(qr, R[idkl]);
// debug(idkl, idkr, 1);
while(ql < idkl || qr > idkr){
while(ql < idkl){
idkl--;
ql = min(ql, L[idkl]);
qr = max(qr, R[idkl]);
}
while(idkr < qr){
idkr++;
ql = min(ql, L[idkr]);
qr = max(qr, R[idkr]);
}
// debug(idkl, idkr);
}
}
if (qr != r) markl = true;
// debug(1);
int cntr = 0;
bool markr = false;
idkl = l, idkr = r;
int ql2 = l, qr2 = r;
// debug(idkr, tr);
while(idkr < tr && ql2 == l){
idkr++;
cntr++;
ql2 = min(ql2, L[idkr]);
qr2 = max(qr2, R[idkr]);
// debug(idkl, idkr, 1);
while(ql2 < idkl || qr2 > idkr){
while(ql2 < idkl){
idkl--;
ql2 = min(ql2, L[idkl]);
qr2 = max(qr2, R[idkl]);
}
while(idkr < qr2){
idkr++;
ql2 = min(ql2, L[idkr]);
qr2 = max(qr2, R[idkr]);
}
// debug(idkl, idkr);
}
}
if (ql2 != l) markr = true;
// debug(markl, markr, cntl, cntr);
if (markl && markr){
if (cntl < cntr){
l = ql;
r = qr;
ans += 2*cntl;
}
else{
l = ql2;
r = qr2;
ans += 2*cntr;
}
}
else{
l = tl;
r = tr;
ans += 2*cntl + 2*cntr;
}
}
return ans;
}
ll minimum_walk(vector<int> p, int s) {
n = p.size();
int mn = s, mx = s;
ll ans = 0;
for (int i = 0; i < n; i++){
a[i] = p[i];
if (a[i] != i){
mn = min(mn, i);
mx = max(mx, i);
}
ans += abs(a[i] - i);
}
for (int i = 0; i < n; i++){
vector<int> tmp;
int x = i;
while(!vis[x]){
vis[x] = true;
tmp.push_back(x);
x = a[x];
}
// debug(i);
//for (auto x: tmp) debug(x);
sort(all(tmp));
for (auto x: tmp){
L[x] = tmp[0];
R[x] = tmp.back();
// debug(x, L[x], R[x]);
}
}
return ans + solve(s, s, mn, mx);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
304 KB |
Output is correct |
| 2 |
Correct |
1 ms |
308 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
304 KB |
Output is correct |
| 2 |
Correct |
1 ms |
308 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
304 KB |
Output is correct |
| 2 |
Correct |
1 ms |
308 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
3rd lines differ - on the 1st token, expected: '3304', found: '3306' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
304 KB |
Output is correct |
| 2 |
Correct |
1 ms |
308 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
3rd lines differ - on the 1st token, expected: '8', found: '10' |
| 4 |
Halted |
0 ms |
0 KB |
- |
