Submission #1214136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214136		PenguinsAreCute	Tourism (JOI23_tourism)	C++17	28 / 100	5095 ms	28220 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
#define all(v) begin(v),end(v)
#define REP(i,a,b) for(int i=a;i<b;i++)
#pragma GCC optimize("O3")
using ii = pair<int,int>;
struct fenwick {
	int n;
	vector<int> fw;
	fenwick(int _n): n(_n+1), fw(_n+1) {}
	void up(int x, int u) {
		for(++x;x<n;x+=(x&(-x)))
			fw[x] += u;
	}
	int qry(int x) {
		int ans = 0;
		for(++x;x;x-=(x&(-x)))
			ans += fw[x];
		return ans;
	}
	int bsta(int x) {
		int ans = 0;
		for(int i=18;i--;)
			if((ans|(1<<i))<n && fw[ans|(1<<i)] <= x)
				x -= fw[ans |= (1 << i)];
		return ans;
	}
};
struct setwick {
	fenwick f; int n;
	setwick(int _n): n(_n), f(_n) {}
	void ins(int x) {f.up(x, 1);}
	void rem(int x) {f.up(x, -1);}
	int ord(int x) {return f.qry(x-1);}
	int kth(int k) {return f.bsta(k);}
	int sz() {return f.qry(n-1);}
};
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> h(n,0), euler(n), pre(n), inv(n), c(m);
	vector<vector<int>> adj(n);

	REP(i,1,n) {
		int a, b;
		cin >> a >> b;
		adj[a-1].push_back(b-1);
		adj[b-1].push_back(a-1);
	}

	vector<vector<int>> sparse(18,vector<int>(2*n,0));
	auto dfs = [cnt1=0,cnt2=0,&sparse,&adj,&h,&euler,&pre,&inv](auto &self, int x, int p) mutable -> void {
		inv[pre[x] = cnt1++] = x;
		sparse[0][euler[x] = cnt2++] = h[x];
		for(auto i: adj[x])
			if(i != p) {
				h[i] = h[x] + 1;
				self(self, i, x);
				sparse[0][cnt2++] = h[x];
			}
	};
	dfs(dfs, 0, -1);
	for(int i=1;i<18;i++)
		for(int j=0;j<=2*n-(1<<i);j++)
			sparse[i][j] = min(sparse[i-1][j],sparse[i-1][j+(1<<(i-1))]);

	auto lca = [&sparse,&euler,&inv](int a, int b) {
		a = euler[inv[a]];
		b = euler[inv[b]];
		if(a > b)
			swap(a, b);
		int l = 31 ^ __builtin_clz(b - a + 1);
		return min(sparse[l][a], sparse[l][b-(1<<l)+1]);
	};


	REP(i,0,m) {
		cin >> c[i];
		c[i]--;
	}

	setwick s(n);
	auto val = [&s,&h,&inv,&lca](int pos, int val) {
		int ans = h[inv[val]];
		int sz = s.sz();
		if(sz == 1)
			return 0;
		if(pos == 0) {
			int nxt = s.kth(1);
			int r1 = lca(nxt,s.kth(sz-1));
			int r2 = lca(val,nxt);
			ans += r1 - r2 - min(r1, r2);
		} else if(pos == sz - 1) {
			int prv = s.kth(sz-2);
			int r1 = lca(s.kth(0),prv);
			int r2 = lca(prv,val);
			ans += r1 - r2 - min(r1, r2);
		} else {
			int r1 = lca(val,s.kth(pos+1));
			int r2 = lca(s.kth(pos-1),val);
			ans += min(r1, r2) - r1 - r2;
		}
		return ans;
	};
	auto ins = [&s,&val,&inv](int x) -> int {
		s.ins(x);
		return val(s.ord(x), x);
	};
	auto rem = [&s,&val,&inv](int x) -> int {
		int ans = -val(s.ord(x), x);
		s.rem(x);
		return ans;
	};

	auto qry = [cl=0,cr=-1,ans=1,&c,&pre,&ins,&rem](int ql, int qr) mutable -> int {
		while(cr < qr) {
			cr++;
			ans += ins(pre[c[cr]]);
		}
		while(cl > ql) {
			cl--;
			ans += ins(pre[c[cl]]);
		}
		while(cr > qr) {
			ans += rem(pre[c[cr]]);
			cr--;
		}
		while(cl < ql) {
			ans += rem(pre[c[cl]]);
			cl++;
		}
		return ans;
	};

	vector<array<int,3>> qrs(q);
	REP(i,0,q) {
		cin >> qrs[i][0] >> qrs[i][1];
		qrs[i][0]--;
		qrs[i][1]--;
		qrs[i][2] = i;
	}
	sort(all(qrs),[](array<int,3> a, array<int,3> b) {
		if(a[0]/300 == b[0]/300)
			return ((a[0]/300)&1?a[1]<b[1]:a[1]>b[1]);
		return a[0]<b[0];
	});
	vector<int> ans(q);
	REP(i,0,q)
		ans[qrs[i][2]] = qry(qrs[i][0], qrs[i][1]);
	for(int i=0;i<q;i++)
		cout << ans[i] << "\n";
}

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