Submission #125375

#	Time	Username	Problem	Language	Result	Execution time	Memory
125375		choikiwon	Railway Trip (JOI17_railway_trip)	C++17	30 / 100	1194 ms	524292 KiB

railway_trip

#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 (stderr)

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 / 5
• Subtask 2: 0 / 15
• Subtask 3: 25 / 25
• Subtask 4: 0 / 55