Submission #413504

#	Time	Username	Problem	Language	Result	Execution time	Memory
413504		Tc14	Inside information (BOI21_servers)	C++17	55 / 100	705 ms	74232 KiB

servers

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;
const int L = 20;

struct path {
    bool asc, dec;
    int min, max;
};

path combine(path a, path b) {

    bool asc, dec;

    if (a.min == -1) return b;
    if (b.min == -1) return a;

    asc = a.asc && b.asc && a.max < b.min;

    dec = a.dec && b.dec && a.min > b.max;

    return {asc, dec, min(a.min, b.min), max(a.max, b.max)};
}

ve<int> D;
ve<ve<int>> A;
ve<ve<pii>> G;
ve<ve<path>> X;

void f(int u, int p, int s, int d) {

    int a = p;
    path x = {true, true, s, s};
    for (int i = 0; i < L; i++) {

        A[u][i] = a;
        X[u][i] = x;

        if (a != -1) {
            x = combine(x, X[a][i]);
            a = A[a][i];
        }
    }
    D[u] = d;

    for (pii e : G[u]) {
        int v, t;
        tie(v, t) = e;
        if (v != p) f(v, u, t, d + 1);
    }
}

int lca(int a, int b) {

    bool swp = false;
    if (D[a] < D[b]) {
        swap(a, b);
        swp = true;
    }

    path xa = {true, true, -1, -1};
    path xb = {true, true, -1, -1};

    for (int i = L - 1; i >= 0; i--) {
        if (D[a] - (1 << i) >= D[b]) {
            xa = combine(xa, X[a][i]);
            a = A[a][i];
        }
    }

    if (a != b) {

        for (int i = L - 1; i >= 0; i--) {

            if (A[a][i] != A[b][i]) {

                xa = combine(xa, X[a][i]);
                a = A[a][i];

                xb = combine(xb, X[b][i]);
                b = A[b][i];
            }
        }

        xa = combine(xa, X[a][0]);
        xb = combine(xb, X[b][0]);
    }

    if (swp) swap(xa, xb);

    swap(xb.asc, xb.dec);
    path x = combine(xa, xb);

    if (x.asc) return x.max;
    else return INF;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, k, a, b, d, t;
    ve<tuple<int, int, int, int>> Q;
    ve<int> Z, Left, Right;

    cin >> n >> k;

    D = ve<int>(n);
    A = ve<ve<int>>(n, ve<int>(L));
    G = ve<ve<pii>>(n);
    X = ve<ve<path>>(n, ve<path>(L));

    Z = ve<int>(n - 1);
    Left = ve<int>(n);
    Right = ve<int>(n);

    t = 0;
    for (int i = 0; i < n + k - 1; i++) {

        char c;
        cin >> c;

        if (c == 'S') {
            cin >> a >> b;
            a--;
            b--;
            t++;
            G[a].push_back({b, t});
            G[b].push_back({a, t});
            Z[min(a, b)] = t;
        }
        else if (c == 'Q') {
            cin >> a >> d;
            a--;
            d--;
            Q.push_back({1, a, d, t});
        }
        else {
            cin >> d;
            d--;
            Q.push_back({2, d, t, 0});
        }
    }

    f(0, -1, -1, 0);

    int prev = INF;
    int cnt = 0;
    Left[0] = 0;
    for (int i = 0; i < n - 1; i++) {
        if (Z[i] < prev) cnt++;
        else cnt = 1;
        Left[i + 1] = cnt;
        prev = Z[i];
    }

    prev = INF;
    cnt = 0;
    Right[n - 1] = 0;
    for (int i = n - 2; i >= 0; i--) {
        if (Z[i] < prev) cnt++;
        else cnt = 1;
        Right[i] = cnt;
        prev = Z[i];
    }

/*
    cout << " ";
    for (int i = 0; i < n - 1; i++) cout << Z[i] << " ";
    cout << endl;

    for (int i = 0; i < n; i++) cout << Left[i] << " ";
    cout << endl;

    for (int i = 0; i < n; i++) cout << Right[i] << " ";
    cout << endl;
*/

    for (int i = 0; i < k; i++) {
        if (get<0>(Q[i]) == 1) {
            tie(ignore, a, d, t) = Q[i];
            int r = lca(d, a);
            if (r <= t) cout << "yes" << endl;
            else cout << "no" << endl;
        }
        else {

            int ans = 1;
            tie(ignore, d, t, ignore) = Q[i];

            //cout << d << " " << t << endl;

            if (Left[d] != 0) {

                auto y = Z.begin() + d;
                auto x = y - Left[d];

                auto it = lower_bound(x, y, t, greater<int>());
                int inc = (int)distance(it, y);

                ans += inc;

                //cout << inc << "  " << distance(Z.begin(), it) << endl;
            }

            if (Right[d] != 0) {
                auto x = Z.begin() + d;
                auto y = x + Right[d];

                auto it = upper_bound(x, y, t);
                int inc = (int)distance(x, it);

                ans += inc;

                //cout << inc << "  " << distance(Z.begin(), it) << endl;
            }

            cout << ans << endl;
        }
    }

    return 0;
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5