제출 #1224509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224509		ByeWorld	Tourism (JOI23_tourism)	C++20	100 / 100	268 ms	33096 KiB

tourism

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
// #define int long long
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define POP __builtin_popcount
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
const int MAXN = 1e5+10;
const int SQRT = 300;
const int INF = 1e9;
const int MOD = 1e9+7;
const int LOG = 20;
int sum(int a, int b){ a%=MOD; b%=MOD; return (a+MOD+b)%MOD; }
void chsum(int &a, int b){ a%=MOD; b%=MOD; a = (a+MOD+b)%MOD; }
int mul(int a, int b){ return (a*b)%MOD; }
int expo(int a, int b){
	if(b==0) return 1;
	int te = expo(a, b/2); te = mul(te,te);
	return (b%2 ? mul(te,a) : te);
}
void chmul(int &a, int b){ a = (a*b)%MOD; }
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }

int n, m, q, b[MAXN];
int dep[MAXN], sub[MAXN], par[MAXN];
vector<int> tree[MAXN], adj[MAXN];

void dfs(int nw, int pa){
	dep[nw] = dep[pa]+1; sub[nw] = 1; par[nw] = pa;
	for(auto nx : tree[nw]){
		if(nx==pa) continue;
		dfs(nx,nw);
		adj[nw].pb(nx);
		sub[nw] += sub[nx];
	}
}
int root[MAXN];
void bd(int nw, int roo){
	root[nw] = roo;
	if(adj[nw].empty()) return;
	bd(adj[nw][0], roo);

	for(int j=1; j<adj[nw].size(); j++)
		bd(adj[nw][j], adj[nw][j]);
}
struct seg {
	int st[MAXN];
	int que(int x){
		int te = 0;
		for(; x; x-=x&-x) te += st[x];
		return te;
	}
	void upd(int x, int p){
		for(; x<=MAXN-10; x+=x&-x) st[x] += p;
	}
} A;
vector<pii> que[MAXN];
int mn[MAXN], ans[MAXN];
set <ipii> s[MAXN];

void ins(int idx, int l, int r, int val){
	if(l > r) assert(false);

	vector<ipii> pend;
	auto it = s[idx].lower_bound(ipii(pii(r, INF), INF) );

	if(it != s[idx].begin()){
		it--; // ini yg di belakangnya
		for(; true; ){
			bool done = 0;

			auto [xx, v] = *it;
			auto [le, ri] = xx;

			if(max(le,l) > min(ri,r)) break; // gk berpot

			auto it2 = it; 
			if(it != s[idx].begin()) it--;
			else done = 1;
			s[idx].erase(it2);

			A.upd(v, -(ri-le+1) );

			if(l<=le && ri<=r){
				if(done) break;
				continue;
			}

			if(le <= l <= r <= ri){ // tengah
				if(le <= l-1){
					A.upd(v, l-le );
					pend.pb({{le, l-1}, v});
				}

				if(r+1 <= ri){
					A.upd(v, ri-r );
					pend.pb({{r+1, ri}, v});
				}

			} else if(le <= r <= ri){ // di kiri
				if(r+1 <= ri){
					A.upd(v, ri-r );
					pend.pb({{r+1, ri}, v});
				}

			} else if(le <= l <= ri){ // di kanan
				if(le <= l-1){
					A.upd(v, l-le );
					pend.pb({{le, l-1}, v});
				}

			} else assert(false);
			
			if(done) break;
		}
	}

	for(auto in : pend) s[idx].insert(in);
	s[idx].insert({{l,r}, val});
	A.upd(val, r-l+1);
}
void upd(int x, int y, int val){
	while(root[x] != root[y]){
		if(dep[root[x]] > dep[root[y]]) swap(x, y);
		// cout << x << ' ' << y << " xy\n";
		// y naikin
		int roo = root[y];
		ins(roo, dep[roo], dep[y], val);

		y = par[root[y]];
	}
	if(dep[x] > dep[y]) swap(x, y);

	if(dep[x]+1 <= dep[y]){
		ins(root[x], dep[x]+1, dep[y], val);
		// cout << val << " val\n";
		// for(auto [p, val] : s[1]){
		// 	cout << p.fi << ' ' << p.se << ' ' << val << " range\n";
		// }
		// cout << '\n';
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1; i<=n-1; i++){
		int x, y; cin>>x>>y;
		tree[x].pb(y); tree[y].pb(x);
	}
	dfs(1,0);
	for(int i=1; i<=n; i++){
		if(adj[i].empty()) continue;

		for(int j=1; j<adj[i].size(); j++)
			if(sub[ adj[i][j] ] > sub[adj[i][0]])
				swap(adj[i][j], adj[i][0]);
	}
	bd(1,1);

	for(int i=1; i<=m; i++) cin>>b[i];

	for(int X=1; X<=q; X++){
		int l, r; cin>>l>>r;
		if(l==r) ans[X] = 1;
		else que[l].pb({r, X});
	}

	for(int i=m-1; i>=1; i--){
		// upd b[i] - b[i+1]
		// cout << i << " i\n";
		upd(b[i], b[i+1], i);
		// cout << i << " i done\n\n";

		for(auto [r, idx] : que[i]){
			ans[idx] = A.que(r-1)+1;
		}
		// cout << i << " i\n";
		// for(int j=1; j<=n; j++) cout << mn[j] << " \n"[j==n];
	}

	cout << '\n';
	for(int i=1; i<=q; i++) cout << ans[i] << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41