Submission #1300538

#TimeUsernameProblemLanguageResultExecution timeMemory
1300538Hamed_Ghaffari동기화 (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...