Submission #1300538

#TimeUsernameProblemLanguageResultExecution timeMemory
1300538Hamed_GhaffariSynchronization (JOI13_synchronization)C++20
30 / 100
755 ms7948 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector <pair<ll, ll>> vp;
typedef pair<ll, ll> pll;
typedef map <ll, ll> mll;
typedef set <ll> sll;
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define print(x) for (auto i : x) cout << i << ' '; cout << '\n';
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
 
const ll maxn = 2e5+5;
const ll mod = 1e9+7;
const ll inf = 2e18;
 
ll pw(ll a, ll b, ll M = mod) {ll ans = 1; for (; b; a = ((a * a) % M), b >>= 1) if (b & 1) ans = (ans * a) % M; return ans;}
 
ll n, m, q, a[maxn], mn[4*maxn], mx[4*maxn], sum[4*maxn];
 
void upd(ll id, ll l, ll r, ll p) {
    if (r - l == 1) {
        sum[id] = 1 - sum[id];
        return;
    }
 
    ll mid = (l+r)/2;
 
    if (p < mid) upd(2*id, l, mid, p);
    else upd(2*id+1, mid, r, p);
 
    sum[id] = sum[2*id] + sum[2*id+1];
}
 
ll get(ll id, ll l, ll r, ll s, ll e) {
    if (s >= r || e <= l) return 0;
    if (s <= l && e >= r) return sum[id];
 
    ll mid = (l+r)/2;
 
    return get(2*id, l, mid, s, e) + get(2*id+1, mid, r, s, e);
}
 
void updMin(ll id, ll l, ll r, ll s, ll e, ll v) {
    if (mn[id] == 0) mn[id] = inf;
 
    if (s >= r || e <= l) return;
    if (s <= l && e >= r) {
        mn[id] = min(mn[id], v);
        return;
    }
 
    ll mid = (l+r)/2;
 
    updMin(2*id, l, mid, s, e, v);
    updMin(2*id+1, mid, r, s, e, v);
}
 
ll getMin(ll id, ll l, ll r, ll p) {
    if (r - l == 1) return mn[id];
 
    ll mid = (l+r)/2;
    if (p < mid) return min(mn[id], getMin(2*id, l, mid, p));
    return min(mn[id], getMin(2*id+1, mid, r, p));
}
 
void updMax(ll id, ll l, ll r, ll s, ll e, ll v) {
    if (s >= r || e <= l) return;
    if (s <= l && e >= r) {
        mx[id] = max(mx[id], v);
        return;
    }
 
    ll mid = (l+r)/2;
 
    updMax(2*id, l, mid, s, e, v);
    updMax(2*id+1, mid, r, s, e, v);
}
 
ll getMax(ll id, ll l, ll r, ll p) {
    if (r - l == 1) return mx[id];
 
    ll mid = (l+r)/2;
    if (p < mid) return max(mx[id], getMax(2*id, l, mid, p));
    return max(mx[id], getMax(2*id+1, mid, r, p));
}
 
int main() {
    FastIO
 
    cin >> n >> m >> q;
 
    for (ll i = 1; i < n; i++) {
        ll v, u;
        cin >> v >> u;
    }
 
    for (ll i = 1; i <= n; i++) {
        updMin(1, 1, n+1, i, i+1, i);
        updMax(1, 1, n+1, i, i+1, i);
    }
 
    for (ll i = 1; i <= m; i++) {
        ll p;
        cin >> p;
 
        upd(1, 1, n+1, p);
        a[p] = 1 - a[p];
 
        if (a[p] == 1) {
            ll s = 0, e = 0, l = 1, r = p-1;
 
            if (get(1, 1, n+1, p-1, p) == 0) s = p;
            else if (get(1, 1, n+1, 1, p) == p-1) {
                s = 1;
            } else {
                while (r - l > 1) {
                    ll mid = (l+r)/2;
                    if (get(1, 1, n+1, mid, p) == p-mid) r = mid;
                    else l = mid;
                }
 
                s = r;
            }
 
            l = p, r = n;
            while (r - l > 1) {
                ll mid = (l+r)/2;
                if (get(1, 1, n+1, p, mid+1) == mid-p+1) l = mid;
                else r = mid;
            }
            e = l+1;
 
            updMin(1, 1, n+1, s, e+1, getMin(1, 1, n+1, s));
            updMax(1, 1, n+1, s, e+1, getMax(1, 1, n+1, e));
        }
    }
 
    while (q--) {
        ll p; cin >> p;
 
        cout << getMax(1, 1, n+1, p) - getMin(1, 1, n+1, p) + 1 << '\n';
    }
 
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...