oj.uz

Submission #379688

# Submission time Handle Problem Language Result Execution time Memory
379688 2021-03-19T02:58:47 Z fhvirus Birthday gift (IZhO18_treearray) C++17
100 / 100
 1031 ms 63844 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], 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], l[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){
			l[p-1] = LCA(a[p-1], a[p]);
			isl[l[p-1]].emplace(p-1);
		}
		if(p < m){
			l[p] = LCA(a[p], a[p+1]);
			isl[l[p]].emplace(p);
		}
	};

	auto rem = [](int p){
		pos[a[p]].erase(p);
		if(p > 1){
			isl[l[p-1]].erase(p-1);
		}
		if(p < m){
			isl[l[p]].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 16 ms 23916 KB n=5
2 Correct 17 ms 23916 KB n=100
3 Correct 16 ms 23916 KB n=100
4 Correct 16 ms 23916 KB n=100
5 Correct 18 ms 23916 KB n=100
6 Correct 17 ms 24064 KB n=100
7 Correct 17 ms 23916 KB n=100
8 Correct 17 ms 23916 KB n=100
9 Correct 17 ms 23916 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 17 ms 23916 KB n=100
14 Correct 17 ms 23916 KB n=100
15 Correct 16 ms 23916 KB n=100
16 Correct 17 ms 23916 KB n=100
17 Correct 17 ms 23916 KB n=100
18 Correct 16 ms 23916 KB n=100
19 Correct 16 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 16 ms 23916 KB n=100
26 Correct 17 ms 23916 KB n=12
27 Correct 16 ms 23916 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23916 KB n=5
2 Correct 17 ms 23916 KB n=100
3 Correct 16 ms 23916 KB n=100
4 Correct 16 ms 23916 KB n=100
5 Correct 18 ms 23916 KB n=100
6 Correct 17 ms 24064 KB n=100
7 Correct 17 ms 23916 KB n=100
8 Correct 17 ms 23916 KB n=100
9 Correct 17 ms 23916 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 17 ms 23916 KB n=100
14 Correct 17 ms 23916 KB n=100
15 Correct 16 ms 23916 KB n=100
16 Correct 17 ms 23916 KB n=100
17 Correct 17 ms 23916 KB n=100
18 Correct 16 ms 23916 KB n=100
19 Correct 16 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 16 ms 23916 KB n=100
26 Correct 17 ms 23916 KB n=12
27 Correct 16 ms 23916 KB n=100
28 Correct 19 ms 24044 KB n=500
29 Correct 18 ms 24044 KB n=500
30 Correct 17 ms 23916 KB n=500
31 Correct 17 ms 23936 KB n=500
32 Correct 17 ms 23916 KB n=500
33 Correct 17 ms 23916 KB n=500
34 Correct 18 ms 23916 KB n=500
35 Correct 18 ms 23916 KB n=500
36 Correct 17 ms 23916 KB n=500
37 Correct 17 ms 23916 KB n=500
38 Correct 17 ms 23916 KB n=500
39 Correct 18 ms 23916 KB n=500
40 Correct 17 ms 23916 KB n=500
41 Correct 17 ms 23916 KB n=500
42 Correct 18 ms 23916 KB n=500
43 Correct 17 ms 23916 KB n=500
44 Correct 17 ms 23916 KB n=500
45 Correct 17 ms 24044 KB n=500
46 Correct 17 ms 23916 KB n=500
47 Correct 18 ms 23916 KB n=500
48 Correct 17 ms 23916 KB n=500
49 Correct 19 ms 23916 KB n=500
50 Correct 17 ms 23916 KB n=500
51 Correct 17 ms 23916 KB n=500
52 Correct 17 ms 24044 KB n=500
53 Correct 17 ms 23916 KB n=500
54 Correct 18 ms 23916 KB n=500
55 Correct 17 ms 23916 KB n=278
56 Correct 20 ms 23916 KB n=500
57 Correct 17 ms 24064 KB n=500
58 Correct 17 ms 23916 KB n=500

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23916 KB n=5
2 Correct 17 ms 23916 KB n=100
3 Correct 16 ms 23916 KB n=100
4 Correct 16 ms 23916 KB n=100
5 Correct 18 ms 23916 KB n=100
6 Correct 17 ms 24064 KB n=100
7 Correct 17 ms 23916 KB n=100
8 Correct 17 ms 23916 KB n=100
9 Correct 17 ms 23916 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 17 ms 23916 KB n=100
14 Correct 17 ms 23916 KB n=100
15 Correct 16 ms 23916 KB n=100
16 Correct 17 ms 23916 KB n=100
17 Correct 17 ms 23916 KB n=100
18 Correct 16 ms 23916 KB n=100
19 Correct 16 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 16 ms 23916 KB n=100
26 Correct 17 ms 23916 KB n=12
27 Correct 16 ms 23916 KB n=100
28 Correct 19 ms 24044 KB n=500
29 Correct 18 ms 24044 KB n=500
30 Correct 17 ms 23916 KB n=500
31 Correct 17 ms 23936 KB n=500
32 Correct 17 ms 23916 KB n=500
33 Correct 17 ms 23916 KB n=500
34 Correct 18 ms 23916 KB n=500
35 Correct 18 ms 23916 KB n=500
36 Correct 17 ms 23916 KB n=500
37 Correct 17 ms 23916 KB n=500
38 Correct 17 ms 23916 KB n=500
39 Correct 18 ms 23916 KB n=500
40 Correct 17 ms 23916 KB n=500
41 Correct 17 ms 23916 KB n=500
42 Correct 18 ms 23916 KB n=500
43 Correct 17 ms 23916 KB n=500
44 Correct 17 ms 23916 KB n=500
45 Correct 17 ms 24044 KB n=500
46 Correct 17 ms 23916 KB n=500
47 Correct 18 ms 23916 KB n=500
48 Correct 17 ms 23916 KB n=500
49 Correct 19 ms 23916 KB n=500
50 Correct 17 ms 23916 KB n=500
51 Correct 17 ms 23916 KB n=500
52 Correct 17 ms 24044 KB n=500
53 Correct 17 ms 23916 KB n=500
54 Correct 18 ms 23916 KB n=500
55 Correct 17 ms 23916 KB n=278
56 Correct 20 ms 23916 KB n=500
57 Correct 17 ms 24064 KB n=500
58 Correct 17 ms 23916 KB n=500
59 Correct 20 ms 24300 KB n=2000
60 Correct 20 ms 24300 KB n=2000
61 Correct 20 ms 24300 KB n=2000
62 Correct 21 ms 24300 KB n=2000
63 Correct 20 ms 24300 KB n=2000
64 Correct 21 ms 24300 KB n=2000
65 Correct 20 ms 24300 KB n=2000
66 Correct 23 ms 24300 KB n=2000
67 Correct 24 ms 24172 KB n=2000
68 Correct 21 ms 24300 KB n=2000
69 Correct 20 ms 24300 KB n=2000
70 Correct 19 ms 24300 KB n=2000
71 Correct 20 ms 24300 KB n=2000
72 Correct 20 ms 24300 KB n=2000
73 Correct 22 ms 24300 KB n=2000
74 Correct 20 ms 24220 KB n=1844
75 Correct 19 ms 24300 KB n=2000
76 Correct 20 ms 24300 KB n=2000
77 Correct 20 ms 24172 KB n=2000
78 Correct 20 ms 24172 KB n=2000
79 Correct 20 ms 24172 KB n=2000
80 Correct 21 ms 24428 KB n=2000
81 Correct 20 ms 24300 KB n=2000
82 Correct 20 ms 24172 KB n=2000
83 Correct 20 ms 24300 KB n=2000
84 Correct 20 ms 24300 KB n=2000
85 Correct 21 ms 24300 KB n=2000
86 Correct 21 ms 24300 KB n=2000
87 Correct 20 ms 24300 KB n=2000
88 Correct 20 ms 24300 KB n=2000
89 Correct 20 ms 24300 KB n=2000
90 Correct 20 ms 24300 KB n=2000
91 Correct 20 ms 24300 KB n=2000
92 Correct 782 ms 55532 KB n=200000
93 Correct 948 ms 59724 KB n=200000
94 Correct 912 ms 62572 KB n=200000
95 Correct 787 ms 55264 KB n=200000
96 Correct 742 ms 55176 KB n=200000
97 Correct 952 ms 58604 KB n=200000
98 Correct 776 ms 55140 KB n=200000
99 Correct 955 ms 54668 KB n=200000
100 Correct 787 ms 55140 KB n=200000
101 Correct 900 ms 63844 KB n=200000
102 Correct 510 ms 56172 KB n=200000
103 Correct 525 ms 56196 KB n=200000
104 Correct 504 ms 56300 KB n=200000
105 Correct 532 ms 56044 KB n=200000
106 Correct 533 ms 56096 KB n=200000
107 Correct 557 ms 56016 KB n=200000
108 Correct 842 ms 54892 KB n=200000
109 Correct 869 ms 55148 KB n=200000
110 Correct 879 ms 55148 KB n=200000
111 Correct 817 ms 55144 KB n=200000
112 Correct 910 ms 62956 KB n=200000
113 Correct 1014 ms 58476 KB n=200000
114 Correct 773 ms 55136 KB n=200000
115 Correct 1031 ms 56172 KB n=200000
116 Correct 726 ms 55364 KB n=200000
117 Correct 872 ms 62700 KB n=200000
118 Correct 967 ms 56940 KB n=200000
119 Correct 688 ms 54752 KB n=200000
120 Correct 847 ms 63340 KB n=200000
121 Correct 861 ms 63212 KB n=200000
122 Correct 814 ms 63732 KB n=200000
123 Correct 531 ms 55020 KB n=200000
124 Correct 280 ms 35632 KB n=25264