oj.uz

Submission #379674

# Submission time Handle Problem Language Result Execution time Memory
379674 2021-03-19T02:29:02 Z fhvirus Birthday gift (IZhO18_treearray) C++17
100 / 100
 1424 ms 80236 KB 
// 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], anc[L][N];

void dfs(int u, int p = -1){
	for(int v: adj[u])
		if(v != p){
			dep[v] = dep[u] + 1;
			anc[0][v] = u;
			dfs(v, u);
		}
}
void makeLCA(){
	FOO(l,1,L-1) FOO(i,1,n)
		anc[l][i] = anc[l-1][anc[l-1][i]];
}
int LCA(int a, int b){
	if(dep[a] < dep[b]) swap(a, b);

	for(int d = dep[a] - dep[b], l = L - 1; l >= 0; --l)
		if(d >> l & 1) a = anc[l][a];

	if(a == b) return a;

	for(int l = L - 1; l >= 0; --l)
		if(anc[l][a] != anc[l][b]){
			a = anc[l][a];
			b = anc[l][b];
		}

	return anc[0][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);
	}
	dfs(1);
	makeLCA();

	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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB n=5
2 Correct 17 ms 23916 KB n=100
3 Correct 19 ms 24044 KB n=100
4 Correct 21 ms 23916 KB n=100
5 Correct 16 ms 23916 KB n=100
6 Correct 17 ms 23916 KB n=100
7 Correct 17 ms 23916 KB n=100
8 Correct 16 ms 23916 KB n=100
9 Correct 17 ms 24192 KB n=100
10 Correct 16 ms 23916 KB n=100
11 Correct 16 ms 23916 KB n=100
12 Correct 16 ms 23916 KB n=100
13 Correct 16 ms 23916 KB n=100
14 Correct 16 ms 24044 KB n=100
15 Correct 17 ms 23916 KB n=100
16 Correct 16 ms 24040 KB n=100
17 Correct 16 ms 23916 KB n=100
18 Correct 16 ms 23916 KB n=100
19 Correct 17 ms 23916 KB n=100
20 Correct 17 ms 23916 KB n=100
21 Correct 17 ms 23916 KB n=100
22 Correct 17 ms 23916 KB n=100
23 Correct 18 ms 23916 KB n=100
24 Correct 17 ms 23916 KB n=100
25 Correct 17 ms 23916 KB n=100
26 Correct 17 ms 23916 KB n=12
27 Correct 17 ms 23916 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB n=5
2 Correct 17 ms 23916 KB n=100
3 Correct 19 ms 24044 KB n=100
4 Correct 21 ms 23916 KB n=100
5 Correct 16 ms 23916 KB n=100
6 Correct 17 ms 23916 KB n=100
7 Correct 17 ms 23916 KB n=100
8 Correct 16 ms 23916 KB n=100
9 Correct 17 ms 24192 KB n=100
10 Correct 16 ms 23916 KB n=100
11 Correct 16 ms 23916 KB n=100
12 Correct 16 ms 23916 KB n=100
13 Correct 16 ms 23916 KB n=100
14 Correct 16 ms 24044 KB n=100
15 Correct 17 ms 23916 KB n=100
16 Correct 16 ms 24040 KB n=100
17 Correct 16 ms 23916 KB n=100
18 Correct 16 ms 23916 KB n=100
19 Correct 17 ms 23916 KB n=100
20 Correct 17 ms 23916 KB n=100
21 Correct 17 ms 23916 KB n=100
22 Correct 17 ms 23916 KB n=100
23 Correct 18 ms 23916 KB n=100
24 Correct 17 ms 23916 KB n=100
25 Correct 17 ms 23916 KB n=100
26 Correct 17 ms 23916 KB n=12
27 Correct 17 ms 23916 KB n=100
28 Correct 17 ms 24044 KB n=500
29 Correct 17 ms 24044 KB n=500
30 Correct 18 ms 24044 KB n=500
31 Correct 17 ms 24172 KB n=500
32 Correct 17 ms 24044 KB n=500
33 Correct 18 ms 24044 KB n=500
34 Correct 17 ms 24044 KB n=500
35 Correct 17 ms 24044 KB n=500
36 Correct 17 ms 24172 KB n=500
37 Correct 18 ms 24064 KB n=500
38 Correct 18 ms 24172 KB n=500
39 Correct 18 ms 24044 KB n=500
40 Correct 17 ms 24044 KB n=500
41 Correct 18 ms 24044 KB n=500
42 Correct 18 ms 24044 KB n=500
43 Correct 17 ms 24044 KB n=500
44 Correct 18 ms 24172 KB n=500
45 Correct 21 ms 24192 KB n=500
46 Correct 19 ms 24044 KB n=500
47 Correct 17 ms 24044 KB n=500
48 Correct 17 ms 24044 KB n=500
49 Correct 17 ms 24044 KB n=500
50 Correct 18 ms 24064 KB n=500
51 Correct 18 ms 24044 KB n=500
52 Correct 18 ms 24044 KB n=500
53 Correct 18 ms 24044 KB n=500
54 Correct 17 ms 24044 KB n=500
55 Correct 17 ms 24044 KB n=278
56 Correct 20 ms 24044 KB n=500
57 Correct 18 ms 24044 KB n=500
58 Correct 18 ms 24044 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB n=5
2 Correct 17 ms 23916 KB n=100
3 Correct 19 ms 24044 KB n=100
4 Correct 21 ms 23916 KB n=100
5 Correct 16 ms 23916 KB n=100
6 Correct 17 ms 23916 KB n=100
7 Correct 17 ms 23916 KB n=100
8 Correct 16 ms 23916 KB n=100
9 Correct 17 ms 24192 KB n=100
10 Correct 16 ms 23916 KB n=100
11 Correct 16 ms 23916 KB n=100
12 Correct 16 ms 23916 KB n=100
13 Correct 16 ms 23916 KB n=100
14 Correct 16 ms 24044 KB n=100
15 Correct 17 ms 23916 KB n=100
16 Correct 16 ms 24040 KB n=100
17 Correct 16 ms 23916 KB n=100
18 Correct 16 ms 23916 KB n=100
19 Correct 17 ms 23916 KB n=100
20 Correct 17 ms 23916 KB n=100
21 Correct 17 ms 23916 KB n=100
22 Correct 17 ms 23916 KB n=100
23 Correct 18 ms 23916 KB n=100
24 Correct 17 ms 23916 KB n=100
25 Correct 17 ms 23916 KB n=100
26 Correct 17 ms 23916 KB n=12
27 Correct 17 ms 23916 KB n=100
28 Correct 17 ms 24044 KB n=500
29 Correct 17 ms 24044 KB n=500
30 Correct 18 ms 24044 KB n=500
31 Correct 17 ms 24172 KB n=500
32 Correct 17 ms 24044 KB n=500
33 Correct 18 ms 24044 KB n=500
34 Correct 17 ms 24044 KB n=500
35 Correct 17 ms 24044 KB n=500
36 Correct 17 ms 24172 KB n=500
37 Correct 18 ms 24064 KB n=500
38 Correct 18 ms 24172 KB n=500
39 Correct 18 ms 24044 KB n=500
40 Correct 17 ms 24044 KB n=500
41 Correct 18 ms 24044 KB n=500
42 Correct 18 ms 24044 KB n=500
43 Correct 17 ms 24044 KB n=500
44 Correct 18 ms 24172 KB n=500
45 Correct 21 ms 24192 KB n=500
46 Correct 19 ms 24044 KB n=500
47 Correct 17 ms 24044 KB n=500
48 Correct 17 ms 24044 KB n=500
49 Correct 17 ms 24044 KB n=500
50 Correct 18 ms 24064 KB n=500
51 Correct 18 ms 24044 KB n=500
52 Correct 18 ms 24044 KB n=500
53 Correct 18 ms 24044 KB n=500
54 Correct 17 ms 24044 KB n=500
55 Correct 17 ms 24044 KB n=278
56 Correct 20 ms 24044 KB n=500
57 Correct 18 ms 24044 KB n=500
58 Correct 18 ms 24044 KB n=500
59 Correct 21 ms 24428 KB n=2000
60 Correct 21 ms 24556 KB n=2000
61 Correct 21 ms 24556 KB n=2000
62 Correct 20 ms 24428 KB n=2000
63 Correct 25 ms 24428 KB n=2000
64 Correct 21 ms 24428 KB n=2000
65 Correct 21 ms 24428 KB n=2000
66 Correct 21 ms 24556 KB n=2000
67 Correct 21 ms 24428 KB n=2000
68 Correct 23 ms 24556 KB n=2000
69 Correct 24 ms 24428 KB n=2000
70 Correct 20 ms 24428 KB n=2000
71 Correct 20 ms 24428 KB n=2000
72 Correct 20 ms 24428 KB n=2000
73 Correct 20 ms 24428 KB n=2000
74 Correct 20 ms 24556 KB n=1844
75 Correct 20 ms 24428 KB n=2000
76 Correct 21 ms 24428 KB n=2000
77 Correct 21 ms 24428 KB n=2000
78 Correct 21 ms 24492 KB n=2000
79 Correct 21 ms 24428 KB n=2000
80 Correct 21 ms 24556 KB n=2000
81 Correct 25 ms 24556 KB n=2000
82 Correct 22 ms 24428 KB n=2000
83 Correct 20 ms 24556 KB n=2000
84 Correct 20 ms 24428 KB n=2000
85 Correct 21 ms 24428 KB n=2000
86 Correct 24 ms 24428 KB n=2000
87 Correct 25 ms 24428 KB n=2000
88 Correct 20 ms 24556 KB n=2000
89 Correct 20 ms 24556 KB n=2000
90 Correct 20 ms 24556 KB n=2000
91 Correct 20 ms 24448 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23916 KB n=5
2 Correct 17 ms 23916 KB n=100
3 Correct 19 ms 24044 KB n=100
4 Correct 21 ms 23916 KB n=100
5 Correct 16 ms 23916 KB n=100
6 Correct 17 ms 23916 KB n=100
7 Correct 17 ms 23916 KB n=100
8 Correct 16 ms 23916 KB n=100
9 Correct 17 ms 24192 KB n=100
10 Correct 16 ms 23916 KB n=100
11 Correct 16 ms 23916 KB n=100
12 Correct 16 ms 23916 KB n=100
13 Correct 16 ms 23916 KB n=100
14 Correct 16 ms 24044 KB n=100
15 Correct 17 ms 23916 KB n=100
16 Correct 16 ms 24040 KB n=100
17 Correct 16 ms 23916 KB n=100
18 Correct 16 ms 23916 KB n=100
19 Correct 17 ms 23916 KB n=100
20 Correct 17 ms 23916 KB n=100
21 Correct 17 ms 23916 KB n=100
22 Correct 17 ms 23916 KB n=100
23 Correct 18 ms 23916 KB n=100
24 Correct 17 ms 23916 KB n=100
25 Correct 17 ms 23916 KB n=100
26 Correct 17 ms 23916 KB n=12
27 Correct 17 ms 23916 KB n=100
28 Correct 17 ms 24044 KB n=500
29 Correct 17 ms 24044 KB n=500
30 Correct 18 ms 24044 KB n=500
31 Correct 17 ms 24172 KB n=500
32 Correct 17 ms 24044 KB n=500
33 Correct 18 ms 24044 KB n=500
34 Correct 17 ms 24044 KB n=500
35 Correct 17 ms 24044 KB n=500
36 Correct 17 ms 24172 KB n=500
37 Correct 18 ms 24064 KB n=500
38 Correct 18 ms 24172 KB n=500
39 Correct 18 ms 24044 KB n=500
40 Correct 17 ms 24044 KB n=500
41 Correct 18 ms 24044 KB n=500
42 Correct 18 ms 24044 KB n=500
43 Correct 17 ms 24044 KB n=500
44 Correct 18 ms 24172 KB n=500
45 Correct 21 ms 24192 KB n=500
46 Correct 19 ms 24044 KB n=500
47 Correct 17 ms 24044 KB n=500
48 Correct 17 ms 24044 KB n=500
49 Correct 17 ms 24044 KB n=500
50 Correct 18 ms 24064 KB n=500
51 Correct 18 ms 24044 KB n=500
52 Correct 18 ms 24044 KB n=500
53 Correct 18 ms 24044 KB n=500
54 Correct 17 ms 24044 KB n=500
55 Correct 17 ms 24044 KB n=278
56 Correct 20 ms 24044 KB n=500
57 Correct 18 ms 24044 KB n=500
58 Correct 18 ms 24044 KB n=500
59 Correct 21 ms 24428 KB n=2000
60 Correct 21 ms 24556 KB n=2000
61 Correct 21 ms 24556 KB n=2000
62 Correct 20 ms 24428 KB n=2000
63 Correct 25 ms 24428 KB n=2000
64 Correct 21 ms 24428 KB n=2000
65 Correct 21 ms 24428 KB n=2000
66 Correct 21 ms 24556 KB n=2000
67 Correct 21 ms 24428 KB n=2000
68 Correct 23 ms 24556 KB n=2000
69 Correct 24 ms 24428 KB n=2000
70 Correct 20 ms 24428 KB n=2000
71 Correct 20 ms 24428 KB n=2000
72 Correct 20 ms 24428 KB n=2000
73 Correct 20 ms 24428 KB n=2000
74 Correct 20 ms 24556 KB n=1844
75 Correct 20 ms 24428 KB n=2000
76 Correct 21 ms 24428 KB n=2000
77 Correct 21 ms 24428 KB n=2000
78 Correct 21 ms 24492 KB n=2000
79 Correct 21 ms 24428 KB n=2000
80 Correct 21 ms 24556 KB n=2000
81 Correct 25 ms 24556 KB n=2000
82 Correct 22 ms 24428 KB n=2000
83 Correct 20 ms 24556 KB n=2000
84 Correct 20 ms 24428 KB n=2000
85 Correct 21 ms 24428 KB n=2000
86 Correct 24 ms 24428 KB n=2000
87 Correct 25 ms 24428 KB n=2000
88 Correct 20 ms 24556 KB n=2000
89 Correct 20 ms 24556 KB n=2000
90 Correct 20 ms 24556 KB n=2000
91 Correct 20 ms 24448 KB n=2000
92 Correct 1087 ms 68184 KB n=200000
93 Correct 1261 ms 73708 KB n=200000
94 Correct 1218 ms 78572 KB n=200000
95 Correct 1044 ms 68064 KB n=200000
96 Correct 1026 ms 68064 KB n=200000
97 Correct 1307 ms 72440 KB n=200000
98 Correct 1040 ms 68192 KB n=200000
99 Correct 1254 ms 67820 KB n=200000
100 Correct 1090 ms 68124 KB n=200000
101 Correct 1254 ms 79724 KB n=200000
102 Correct 632 ms 68912 KB n=200000
103 Correct 614 ms 68972 KB n=200000
104 Correct 653 ms 69100 KB n=200000
105 Correct 630 ms 69100 KB n=200000
106 Correct 650 ms 69112 KB n=200000
107 Correct 611 ms 68972 KB n=200000
108 Correct 1173 ms 68116 KB n=200000
109 Correct 1148 ms 67940 KB n=200000
110 Correct 1218 ms 68136 KB n=200000
111 Correct 1014 ms 68196 KB n=200000
112 Correct 1178 ms 78572 KB n=200000
113 Correct 1288 ms 72672 KB n=200000
114 Correct 985 ms 68192 KB n=200000
115 Correct 1424 ms 69740 KB n=200000
116 Correct 973 ms 68448 KB n=200000
117 Correct 1189 ms 79084 KB n=200000
118 Correct 1353 ms 71020 KB n=200000
119 Correct 1004 ms 67936 KB n=200000
120 Correct 1109 ms 79660 KB n=200000
121 Correct 1142 ms 79724 KB n=200000
122 Correct 1126 ms 80236 KB n=200000
123 Correct 657 ms 68844 KB n=200000
124 Correct 305 ms 37996 KB n=25264