Submission #1087400

#TimeUsernameProblemLanguageResultExecution timeMemory
1087400coldbr3wTourism (JOI23_tourism)C++17
100 / 100
924 ms37940 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pll pair<long long, long long> #define pb push_back #define F first #define S second #define all(x) (x).begin(), (x).end() const ll N = 3e5 + 100; const ll inf = 1e18; const ll mod = 1e9 + 7; const ll block = 350; ll n,m,q,timer = 0; vector<ll>adj[N]; ll tin[N], heavy[N], sz[N], p[N], head[N], res[N], a[N]; vector<pll>t[N]; set<array<ll,3>>s; struct fenwick_tree{ ll n; vector<ll>ft; void init(ll _n){ n = _n; ft.resize(n + 10); } void update(ll idx, ll val){ while(idx <= n) ft[idx] += val, idx += (idx & (-idx)); } ll get(ll idx){ ll res = 0; while(idx > 0) res += ft[idx], idx -= (idx & (-idx)); return res; } } ft; void dfs(ll u, ll par){ sz[u] = 1; for(auto v : adj[u]){ if(v == par) continue; dfs(v, u); p[v] = u; sz[u] += sz[v]; if(sz[v] > sz[heavy[u]]) heavy[u] = v; } } void HLD(ll u, ll h){ head[u] = h; tin[u] = ++timer; if(heavy[u]) HLD(heavy[u], h); for(auto v : adj[u]){ if(v != p[u] && v != heavy[u]) HLD(v, v); } } void change(ll l, ll r, ll val){ auto it = s.lower_bound({l, l, 0}); if(it != s.begin()) --it; vector<array<ll,3>>del, add; add.pb({l, r, val}); while(it != s.end() && (*it)[0] <= r){ ll l1 = (*it)[0], r1 = (*it)[1], v1 = (*it)[2]; if(r1 < l){ ++it; continue; } del.pb(*it); if(l1 < l) add.pb({l1, l - 1, v1}); if(r1 > r) add.pb({r + 1, r1, v1}); ++it; } for(auto x : del){ ft.update(x[2], -(x[1] - x[0] + 1)); s.erase(x); } for(auto x : add){ ft.update(x[2], x[1] - x[0] + 1); s.insert(x); } } void upd(ll a, ll b, ll val){ for(; head[a] != head[b]; b = p[head[b]]){ if(tin[a] > tin[b]) swap(a, b); change(tin[head[b]], tin[b], val); } if(tin[a] > tin[b]) swap(a, b); change(tin[a], tin[b], val); } void to_thic_cau(){ cin >> n >> m >> q; for(int i = 1; i <= n - 1;i++){ ll u,v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } dfs(1, 0); HLD(1, 1); for(int i = 1; i <= m;i++) cin >> a[i]; for(int i = 1; i <= q;i++){ ll l,r; cin >> l >> r; t[r].pb({l, i}); } s.insert({1, n, 1}); ft.init(m); ft.update(1, m); for(int i = 1; i <= m;i++){ if(i > 1) upd(a[i-1], a[i], i); for(auto x : t[i]){ ll l = x.F, idx = x.S; if(l == i){ res[idx] = 1; continue; } res[idx] = ft.get(i) - ft.get(l); } } for(int i = 1; i <= q;i++) cout << res[i] << '\n'; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); ll tc = 1; //cin >> tc; while(tc--) to_thic_cau(); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...