Submission #379685

#	Time	Username	Problem	Language	Result	Execution time	Memory
379685		fhvirus	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1245 ms	67180 KiB

treearray

// Knapsack DP is harder than FFT.
#include<bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll;
#define ff first
#define ss second
#define pb emplace_back
#define FOR(i,n) for(int i=0;i<(n);++i)
#define FOO(i,a,b) for(int i=(a);i<=int(b);++i)
#define OOF(i,a,b) for(int i=(a);i>=int(b);--i)
#define AI(x) begin(x),end(x)
template<class I>bool chmax(I&a,I b){return a<b?(a=b,true):false;}
template<class I>bool chmin(I&a,I b){return b<a?(a=b,true):false;} 
inline ll cdiv(ll x,ll m){return x/m+(x%m?(x<0)^(m>0):0);}
#ifdef OWO
#define safe cerr<<"\033[1;32m"<<__PRETTY_FUNCTION__<<" - "<<__LINE__<<" JIZZ\033[0m\n"
#define debug(args...) SDF(#args, args)
#define OIU(args...) ostream& operator<<(ostream&O,args)
#define LKJ(S,B,E,F) template<class...T>OIU(S<T...>s){O<<B;int c=0;for(auto i:s)O<<(c++?", ":"")<<F;return O<<E;}
LKJ(vector,'[',']',i)LKJ(deque,'[',']',i)LKJ(set,'{','}',i)LKJ(multiset,'{','}',i)LKJ(unordered_set,'{','}',i)LKJ(map,'{','}',i.ff<<':'<<i.ss)LKJ(unordered_map,'{','}',i.ff<<':'<<i.ss)
template<class T,size_t N>OIU(array<T,N>a){return O<<vector<T>(AI(a));}template<class...T>OIU(pair<T...>p){return O<<'('<<p.ff<<','<<p.ss<<')';}template<class...T>OIU(tuple<T...>t){return O<<'(',apply([&O](T...s){int c=0;(...,(O<<(c++?", ":"")<<s));},t),O<<')';}
template<class...T>void SDF(const char* s,T...a){int c=sizeof...(T);if(!c){cerr<<"\033[1;32mvoid\033[0m\n";return;}(cerr<<"\033[1;32m("<<s<<") = (",...,(cerr<<a<<(--c?", ":")\033[0m\n")));}
#else
#pragma GCC optimize("Ofast")
#define safe ((void)0)
#define debug(...) ((void)0)
#endif
const ll inf = 1e9, INF = 4e18;
const int N = 2e5 + 225, L = 19;
int n, m, q;
vector<int> adj[N];
int dep[N], tio[N], par[N];

void dfs(int u, int p = -1){
	if(p != -1){
		dep[u] = dep[p] + 1;
		par[u] = p;
		if(dep[tio[tio[p]]] - dep[tio[p]] ==
			dep[tio[p]] - dep[p])
			tio[u] = tio[tio[p]];
		else tio[u] = p;
	}
	for(int v: adj[u])
		if(v != p) dfs(v, u);
}
int LCA(int a, int b){
	if(dep[a] < dep[b]) swap(a, b);

	while(dep[a] > dep[b])
		if(dep[tio[a]] >= dep[b]) a = tio[a];
		else a = par[a];

	if(a == b) return a;

	while(par[a] != par[b])
		if(tio[a] != tio[b]){
			a = tio[a];
			b = tio[b];
		} else {
			a = par[a];
			b = par[b];
		}

	return par[a];
}

int a[N];

set<int> pos[N], isl[N];

int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m >> q;
	FOR(_,n-1){
		int u, v; cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	fill(tio, tio + n + 1, 1);
	dfs(1);

	FOO(i,1,m){
		cin >> a[i];
		pos[a[i]].emplace(i);
	}

	auto add = [](int p){
		pos[a[p]].emplace(p);
		if(p > 1){
			int lca = LCA(a[p-1], a[p]);
			isl[lca].emplace(p-1);
		}
		if(p < m){
			int lca = LCA(a[p], a[p+1]);
			isl[lca].emplace(p);
		}
	};

	auto rem = [](int p){
		pos[a[p]].erase(p);
		if(p > 1){
			int lca = LCA(a[p-1], a[p]);
			isl[lca].erase(p-1);
		}
		if(p < m){
			int lca = LCA(a[p], a[p+1]);
			isl[lca].erase(p);
		}
	};

	FOO(i,1,m-1) add(i);

	FOR(_,q){
		int cmd; cin >> cmd;
		if(cmd == 1){
			int p, v; cin >> p >> v;
			rem(p);
			a[p] = v;
			add(p);
		} else {
			int l, r, v; cin >> l >> r >> v;
			auto it = isl[v].lower_bound(l);
			if(it != end(isl[v]) and *it < r){
				cout << *it << ' ' << (*it) + 1 << '\n';
			} else {
				it = pos[v].lower_bound(l);
				int ans = -1;
				if(it != end(pos[v]) and *it <= r)
					ans = *it;
				cout << ans << ' ' << ans << '\n';
			}
		}
	}
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44