oj.uz

Submission #125375

# Submission time Handle Problem Language Result Execution time Memory
125375 2019-07-05T07:10:37 Z choikiwon Railway Trip (JOI17_railway_trip) C++17
30 / 100
 1194 ms 524292 KB 
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MN = 100010;

int N, K, Q;
int L[MN];
vector<int> V[MN];
map<pii, vector<int> > ldist, rdist;

struct BIT {
    vector<int> tree;
    void init() {
        tree = vector<int>(4 * N, -1e9);
    }
    void upd(int x, int v, int l, int r, int n) {
        if(x < l || r < x) return;
        if(l == r) {
            tree[n] = v;
            return;
        }
        int m = (l + r)>>1;
        upd(x, v, l, m, 2*n);
        upd(x, v, m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    int quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return -1e9;
        if(a <= l && r <= b) return tree[n];
        int m = (l + r)>>1;
        int L = quer(a, b, l, m, 2*n);
        int R = quer(a, b, m + 1, r, 2*n + 1);
        return max(L, R);
    }
} bit, sub1, sub2;

void solve(int l, int r) {
    if(l + 1 == r) {
        ldist[ pii(l, r) ] = vector<int>(r - l + 1, 0);
        rdist[ pii(l, r) ] = vector<int>(r - l + 1, 0);
        ldist[ pii(l, r) ][1] = 1;
        rdist[ pii(l, r) ][1] = 1;
        return;
    }

    int x = bit.quer(l + 1, r - 1, 0, N - 1, 1);
    int a = lower_bound(V[x].begin(), V[x].end(), l) - V[x].begin();

    vector<int> P;
    P.push_back(l);
    for(int i = a; i < V[x].size() && V[x][i] < r; i++) P.push_back(V[x][i]);
    P.push_back(r);

    ldist[ pii(l, r) ] = vector<int>(r - l + 1, 0);
    rdist[ pii(l, r) ] = vector<int>(r - l + 1, 0);

    for(int i = 0; i < (int)P.size() - 1; i++) {
        solve(P[i], P[i + 1]);

        for(int j = P[i]; j <= P[i + 1]; j++) {
            int d1 = i + ldist[ pii(P[i], P[i + 1]) ][ j - P[i] ];
            int d2 = (int)P.size() - 2 - i + rdist[ pii(P[i], P[i + 1]) ][ P[i + 1] - j ];
            ldist[ pii(l, r) ][j - l] = min(d1, d2 + 1);
            rdist[ pii(l, r) ][r - j] = min(d1 + 1, d2);
        }
    }
}

struct Query {
    int a, b, id;
};
vector<Query> query[MN];
int ans[MN];

int main() {
    scanf("%d %d %d", &N, &K, &Q);

    for(int i = 0; i < N; i++) {
        scanf("%d", &L[i]);
        V[ --L[i] ].push_back(i);
    }

    bit.init();
    for(int i = 0; i < N; i++) bit.upd(i, L[i], 0, N - 1, 1);

    for(int i = 0; i < (int)V[K - 1].size() - 1; i++) {
        solve(V[K - 1][i], V[K - 1][i + 1]);
    }

    for(int i = 0; i < Q; i++) {
        int a, b; scanf("%d %d", &a, &b);
        a--; b--;
        if(a > b) swap(a, b);


        int x = bit.quer(a, b, 0, N - 1, 1);
        query[x].push_back({ a, b, i });
    }

    sub1.init();
    sub2.init();
    for(int i = K - 1; i >= 0; i--) {
        for(int j = 0; j < query[i].size(); j++) {
            int a = query[i][j].a;
            int b = query[i][j].b;
            int id = query[i][j].id;

            int l = lower_bound(V[i].begin(), V[i].end(), a) - V[i].begin();
            int r = upper_bound(V[i].begin(), V[i].end(), b) - V[i].begin() - 1;
            int pl = sub1.quer(0, a, 0, N - 1, 1);
            int pr = -sub2.quer(b, N - 1, 0, N - 1, 1);

            ans[id] = 1e9;
            if(pl != -1e9 && pr != 1e9) ans[id] = min(ans[id], ldist[ pii(pl, pr) ][a - pl] + rdist[ pii(pl, pr) ][pr - b] + 1);

            int d1, d2;
            if(a == V[i][l]) d1 = 0;
            else {
                if(l) pl = max(pl, V[i][l - 1]);
                d1 = rdist[ pii(pl, V[i][l]) ][ V[i][l] - a ];
            }
            if(b == V[i][r]) d2 = 0;
            else {
                if(r < (int)V[i].size() - 1) pr = min(pr, V[i][r + 1]);
                d2 = ldist[ pii(V[i][r], pr) ][ b - V[i][r] ];
            }
            ans[id] = min(ans[id], d1 + d2 + r - l);
        }

        for(int j = 0; j < V[i].size(); j++) {
            int x = V[i][j];
            sub1.upd(x, x, 0, N - 1, 1);
            sub2.upd(x, -x, 0, N - 1, 1);
        }
    }
    for(int i = 0; i < Q; i++) {
        printf("%d\n", ans[i] - 1);
    }
}

Compilation message

railway_trip.cpp: In function 'int main()':
railway_trip.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &K, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &L[i]);
         ~~~~~^~~~~~~~~~~~~
railway_trip.cpp:93:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d %d", &a, &b);
                   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 6 ms 5240 KB Output is correct
7 Correct 6 ms 5112 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 6 ms 4956 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5584 KB Output is correct
2 Correct 434 ms 49248 KB Output is correct
3 Correct 478 ms 52568 KB Output is correct
4 Correct 517 ms 55672 KB Output is correct
5 Correct 572 ms 57464 KB Output is correct
6 Correct 667 ms 62200 KB Output is correct
7 Correct 817 ms 69452 KB Output is correct
8 Correct 288 ms 33388 KB Output is correct
9 Runtime error 516 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 54264 KB Output is correct
2 Correct 712 ms 52716 KB Output is correct
3 Correct 777 ms 54728 KB Output is correct
4 Correct 743 ms 54960 KB Output is correct
5 Correct 758 ms 55260 KB Output is correct
6 Correct 788 ms 55720 KB Output is correct
7 Correct 739 ms 55940 KB Output is correct
8 Correct 459 ms 41600 KB Output is correct
9 Correct 465 ms 37572 KB Output is correct
10 Correct 1102 ms 51768 KB Output is correct
11 Correct 1183 ms 51680 KB Output is correct
12 Correct 1129 ms 51740 KB Output is correct
13 Correct 1194 ms 51672 KB Output is correct
14 Correct 747 ms 49896 KB Output is correct
15 Correct 627 ms 50664 KB Output is correct
16 Correct 730 ms 51428 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 957 ms 72880 KB Output is correct
2 Correct 989 ms 73600 KB Output is correct
3 Correct 945 ms 69128 KB Output is correct
4 Correct 934 ms 71332 KB Output is correct
5 Correct 474 ms 37476 KB Output is correct
6 Runtime error 473 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -