oj.uz

Submission #228097

# Submission time Handle Problem Language Result Execution time Memory
228097 2020-04-29T21:21:42 Z VEGAnn Ancient Books (IOI17_books) C++14
0 / 100
 2000 ms 384 KB 
#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, P[N];

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++){
        P[i] = p[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;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2081 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -