Submission #1300536

#TimeUsernameProblemLanguageResultExecution timeMemory
1300536Hamed_GhaffariSynchronization (JOI13_synchronization)C++20
30 / 100
178 ms40820 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 2e5+10, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20;
typedef pair<int, int> pii;
 
int n, m, q, L[maxn], R[maxn], f[maxn], lst[maxn];
vector<pii> seg[maxn << 2], OPS;
 
int getF(int v) {
  return f[v] < 0 ? v : getF(f[v]);
}
 
inline void merge(int u, int v) {
  u = getF(u), v = getF(v);
  if (u == v) return;
  if (f[u] > f[v]) swap(u, v);
  OPS.pb({v, f[v]});
  f[u] += f[v];
  f[v] = u;
  L[u] = min(L[u], L[v]);
  R[u] = max(R[u], R[v]);
}
 
inline void undo(int id) {
  while (OPS.size() > id) {
    auto [u, fu] = OPS.back(); OPS.pop_back();
    int v = getF(u);
    L[u] = min(L[u], L[v]);
    R[u] = max(R[u], R[v]);
    f[v] -= fu;
    f[u] = fu;
  }
}
 
void update(int ql, int qr, pii e, int l = 1, int r = maxn, int id = 1) {
  if (ql <= l && r <= qr) return void (seg[id].pb(e));
  if (qr <= l || r <= ql) return;
 
  int mid = (l + r) >> 1, lc = id << 1, rc = lc | 1;
  update(ql, qr, e, l, mid, lc);
  update(ql, qr, e, mid, r, rc);
}
 
void dfs(int id, int l, int r) {
  int ver = OPS.size();
  for (auto [u, v] : seg[id]) merge(u, v);
  if (r - l > 1) {
    int mid = (l + r) >> 1, lc = id << 1, rc = lc | 1;
    dfs(lc, l, mid);
    dfs(rc, mid, r);
  }
  undo(ver); 
}
 
int32_t main() {
  cin.tie(0)->sync_with_stdio(0); 
  cin >> n >> m >> q;
  for (int i = 1 ; i <= n ; i ++) {
    f[i] = -1;
    L[i] = R[i] = i;
  }
  for (int i = 1 , u , v ; i < n ; i ++) {
    cin >> u >> v;
    if (u != i || v != i+1) return 0;
  }
  for (int i = 1 , x ; i <= m ; i ++) {
    cin >> x;
    if (lst[x] == 0) lst[x] = i;
    else {
      update(lst[x], i + 1, pii(x, x+1));
      lst[x] = 0;
    }
  }
 
  for (int i = 1 ; i < n ; i ++) {
    if (lst[i]) update(lst[i], m + 2, pii(i, i+1));
  }
 
  dfs(1, 1, maxn);
  for (int i = 1, v ; i <= q ; i ++) {
    cin >> v;
    cout << R[v] - L[v] + 1 << nl;
  }
}
#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...