| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 228096 | VEGAnn | 고대 책들 (IOI17_books) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "books.h"
//#include "grader.h"
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 1000100;
const ll OO = 1e18;
bool mrk[N];
queue<int> q;
ll ans = 0;
int n, le, ri, mem_l[N], mem_r[N], il[N], ir[N], cl, cr, loc_l, loc_r, S;
void extend(){
while (sz(q)){
int v = q.front(); q.pop();
int nl = v, nr = p[v];
if (nl > nr) swap(nl, nr);
if (nl < le){
for (int j = nl; j < le; j++)
q.push(j);
le = nl;
}
if (nr > ri){
for (int j = ri + 1; j <= nr; j++)
q.push(j);
ri = nr;
}
}
}
void get_lf(){
int lst = le;
loc_l = -1;
cl = 0;
for (int i = le - 1; i >= 0; i--){
if (i < lst) cl += 2;
if (mem_l[i] >= 0)
lst = min(lst, mem_l[i]);
if (ir[i] > S){
loc_l = i;
return;
}
}
}
void get_rt(){
int lst = ri;
loc_r = -1;
cr = 0;
for (int i = ri + 1; i < n; i++){
if (i > lst) cl += 2;
if (mem_r[i] >= 0)
lst = max(lst, mem_l[i]);
if (il[i] < S){
loc_r = i;
return;
}
}
}
long long minimum_walk(std::vector<int> p, int s) {
n = sz(p);
S = s;
bool was = 0;
fill(mem_l, mem_l + n, -1);
fill(mem_r, mem_r + n, -1);
for (int i = 0; i < n; i++){
ans += abs(p[i] - i);
if (p[i] != i) {
was = 1;
int lf = i;
int rt = p[i];
if (lf > rt) swap(lf, rt);
mem_l[rt] = lf;
mem_r[lf] = rt;
}
if (mrk[i]) continue;
int cr = i, mn = i, mx = i;
while (!mrk[cr]){
mn = min(mn, cr);
mx = max(mx, cr);
mrk[cr] = 1;
cr = p[cr];
}
il[i] = mn;
ir[i] = mx;
cr = p[i];
while (cr != i){
il[cr] = mn;
ir[cr] = mx;
cr = p[cr];
}
}
if (!was) return 0;
le = ri = s;
q.push(s);
extend();
while (1){
get_lf();
get_rt();
if (loc_l < 0) continue;
ans += min(cl, cr);
for (int j = loc_l; j < le; j++)
q.push(j);
le = loc_l;
}
return ans;
}