Submission #994557

#	Time	Username	Problem	Language	Result	Execution time	Memory
994557		vjudge1	Synchronization (JOI13_synchronization)	C++17	30 / 100	170 ms	15192 KiB

synchronization

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;

const ll MAXN = 1E5+16;
vector <ii> adj[MAXN];

struct Fenwick {
    vll tree;
    ll n;

    Fenwick (ll n): tree(n, 0), n(n) {}

    void update (ll id, ll val) {
        for (; id < n; id |= id+1)
            tree[id] += val;
    }

    ll query (ll ql, ll qr) { return query(qr) - query(ql-1); }
    ll query (ll id) {
        ll ans = 0;
        for (; id >= 0; id &= id+1, id--) ans += tree[id];
        return ans;
    }
};

ii operator+ (const ii a, const ii b) {
    return {
        min(a.first, b.first),
        max(a.second, b.second)
    };
}

struct SegTree {
    vector <ii> tree;
    ll n;

    SegTree (ll n): tree(2*n, { n, -1 }), n(n) {}

    void update (ll id, ll val, bool atF) {
        id += n;
        if (atF) tree[id].first = val;
        else tree[id].second = val;
        for (; id > 1; id >>= 1) {
            tree[id>>1] = tree[id] + tree[id^1];
        }
    }

    ii query (ll ql, ll qr) {
        ii ans = { n, -1 };
        for (ql += n, qr += n+1; ql < qr; ql >>= 1, qr >>= 1) {
            if (ql&1) ans = ans + tree[ql++];
            if (qr&1) ans = ans + tree[--qr];
        }
        return ans;
    }
};

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, m, Q;
    cin >> n >> m >> Q;
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        u--; v--;
        adj[u].push_back({ v, i });
        adj[v].push_back({ u, i });
    }
    vector <char> isOn(n, false);
    Fenwick ft(n-1);
    SegTree st(n);
    for (ll i = 0; i < n; i++) {
        st.update(i, i, true);
        st.update(i, i, false);
    }
    while (m--) {
        ll at;
        cin >> at;
        at--;
        isOn[at] ^= 1;
        if (!isOn[at]) { ft.update(at, -1); continue; }
        ft.update(at, 1);
        ll f1, l1;
        {ll l = -1, r = at;
        while (l+1 < r) {
            ll mid = ((l+r)>>1);
            if (ft.query(mid, at) == at-mid+1)
                r = mid;
            else
                l = mid;
        }
        f1 = r;}
        {ll l = at, r = n-1;
        while (l+1 < r) {
            ll mid = ((l+r)>>1);
            if (ft.query(at, mid) == mid-at+1)
                l = mid;
            else
                r = mid;
        }
        l1 = l;}
        l1++;
        auto [minN, _1] = st.query(f1, n-1);
        auto [_2, maxN] = st.query(0, l1);
        st.update(l1, minN, true);
        st.update(f1, maxN, false);
    }
    vll ans(n);
    for (ll i = 0; i < n; i++) {
        auto [minN, _1] = st.query(i, n-1);
        auto [_2, maxN] = st.query(0, i);
        ans[i] = maxN-minN+1;
    }
    while (Q--) {
        ll u;
        cin >> u;
        u--;
        cout << ans[u] << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 0 / 40