oj.uz

Submission #638790

# Submission time Handle Problem Language Result Execution time Memory
638790 2022-09-07T13:48:33 Z qwerasdfzxcl Ancient Books (IOI17_books) C++17
12 / 100
 1 ms 340 KB 
#include "books.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int  n, s, ts, ans, a[1001000], cycL[1001000], cycR[1001000], L[1001000], R[1001000], dp[1001000];
bool visited[1001000];
ll cycsum;

struct Seg{
    int tree[2002000], sz;
    void init(int n){
        sz = n;
        fill(tree, tree+sz*2, 1e9);
    }
    void update(int p, int x){
        for (tree[p+=sz]=x;p>1;p>>=1) tree[p>>1] = min(tree[p], tree[p^1]);
    }
    int query(int l, int r){
        int ret = 1e9;
        ++r;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = tree[l++];
            if (r&1) ret = tree[--r];
        }
        return ret;
    }
}tree;

ll myabs(ll x){
    if (x<0) return -x;
    return x;
}


void dfs(int l, int r){
    //printf("dfs: %d %d\n", l, r);
    if (l==L[ts] && r==R[ts]) {ans += dp[L[ts]]; return;}

    vector<pair<int, int>> child;
    for (int i=l+1;i<r;){
        if (R[i]<r){
            child.emplace_back(i, R[i]);
            i = R[i] + 1;
        }
        else i++;
    }

    vector<int> gl = {1}, gr = {1};
    for (int i=1;i<(int)child.size();i++){
        if (child[i-1].second+1==child[i].first) gl.push_back(gl.back()+1);
        else gl.push_back(1);
    }
    for (int i=(int)child.size()-2;i>=0;i--){
        if (child[i].second+1==child[i+1].first) gr.push_back(gr.back()+1);
        else gr.push_back(1);
    }
    reverse(gr.begin(), gr.end());

    for (int i=0;i<(int)child.size();i++) dp[child[i].first] = min(gl[i], gr[i]);
    if (l==0) for (int i=0;i<(int)child.size();i++) dp[child[i].first] = (int)child.size()-1;

    for (auto &[nl, nr]:child) dfs(nl, nr);
}

long long minimum_walk(std::vector<int> P, int S) {
    int si = 0, ei = (int)P.size()-1;
    for(;si<(int)P.size() && P[si]==si;si++);
    for(;ei>=0 && P[ei]==ei;ei--);

    if (si > ei) return 0;
    n = ei-si+1;
    for (int i=si;i<=ei;i++) a[i-si+1] = P[i] - si + 1;
    s = S-si+1;

    for (int i=1;i<=n;i++) if (!visited[i]){
        for (int j=i;!visited[j];j=a[j]){
            visited[j] = 1;
            cycR[i] = max(cycR[i], j);
            cycsum += myabs(j - a[j]);
        }
        cycL[cycR[i]] = i;
    }

    ///calc range
    tree.init(n+1);
    fill(visited+1, visited+n+1, 0);
    for (int i=1;i<=n;i++) if (!visited[i]){
        L[i] = min(tree.query(i, cycR[i]), i);

        for (int j=i;!visited[j];j=a[j]){
            visited[j] = 1;
            L[j] = L[i];
            tree.update(j, L[i]);
        }
    }

    tree.init(n+1);
    fill(visited+1, visited+n+1, 0);
    for (int i=n;i;i--) if (!visited[i]){
        R[i] = max(-tree.query(cycL[i], i), i);

        for (int j=i;!visited[j];j=a[j]){
            visited[j] = 1;
            R[j] = R[i];
            tree.update(j, R[i]);
        }
    }

    //for (int i=1;i<=n;i++) printf("(%d, %d) ", L[i], R[i]);
    //printf("\n");

    if (s<=0) ts = 1, ans = 1-s;
    else if (s>n) ts = n, ans = s-n;
    else ts = s, ans = 0;

    //printf("ok n = %d, s = %d\n", n, s);
    dfs(0, n+1);

    return cycsum + ans * 2;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Incorrect 1 ms 308 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338576'
20 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Incorrect 1 ms 308 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338576'
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Incorrect 1 ms 308 KB 3rd lines differ - on the 1st token, expected: '338572', found: '338576'
20 Halted 0 ms 0 KB -