Submission #911115

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
911115	2024-01-18T13:14:54 Z	oblantis	Global Warming (CEOI18_glo)	C++17	100 / 100	715 ms	48820 KB

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 4e5 + 1;
int tr[maxn * 4], x, xl, xr;
int get(int v, int l, int r){
	if(xl <= l && r <= xr)return tr[v];
	if(r <= xl || xr <= l)return 0;
	return max(get(v * 2 + 1, l, (l + r) / 2), get(v * 2 + 2, (l + r) / 2, r));
}
void upd(int v, int l, int r){
	if(l + 1 == r){
		tr[v] = x;
		return;
	}
	if((l + r) / 2 <= xl)upd(v * 2 + 2, (l + r) / 2, r);
	else upd(v * 2 + 1, l, (l + r) / 2);
	tr[v] = max(tr[v * 2 + 1], tr[v * 2 + 2]);
}
void solve() {
	int n;
	cin >> n >> x;
	int t[n], p[n], sf[n];
	set<int> s;
	map<int, int> m;
	for(int i = 0; i < n; i++){
		cin >> t[i];
		p[i] = t[i] + x;
		s.insert(t[i]);
		s.insert(t[i] + x);
	}
	int cnt = 0;
	for(auto i : s)m[i] = cnt++;
	for(int i = n - 1; i >= 0; i--){
		t[i] = m[t[i]];
		p[i] = m[p[i]];
		xl = t[i] + 1, xr = maxn;
		x = get(0, 0, maxn) + 1;
		xl = t[i];
		sf[i] = x;
		upd(0, 0, maxn);
	}
	memset(tr, 0, sizeof tr);
	int ans = 0;
	for(int i = 0; i < n; i++){
		xl = 0, xr = p[i];
		x = get(0, 0, maxn) + sf[i];
		ans = max(ans, x);
		xl = 0, xr = t[i];
		x = get(0, 0, maxn) + 1;
		xl = t[i];
		upd(0, 0, maxn);
	}
	cout << ans;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	6484 KB	Output is correct
2	Correct	3 ms	6488 KB	Output is correct
3	Correct	3 ms	6492 KB	Output is correct
4	Correct	3 ms	6492 KB	Output is correct
5	Correct	3 ms	6748 KB	Output is correct
6	Correct	3 ms	6492 KB	Output is correct
7	Correct	3 ms	6484 KB	Output is correct
8	Correct	4 ms	6488 KB	Output is correct
9	Correct	3 ms	6492 KB	Output is correct
10	Correct	3 ms	6488 KB	Output is correct
11	Correct	2 ms	6492 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	6484 KB	Output is correct
2	Correct	3 ms	6488 KB	Output is correct
3	Correct	3 ms	6492 KB	Output is correct
4	Correct	3 ms	6492 KB	Output is correct
5	Correct	3 ms	6748 KB	Output is correct
6	Correct	3 ms	6492 KB	Output is correct
7	Correct	3 ms	6484 KB	Output is correct
8	Correct	4 ms	6488 KB	Output is correct
9	Correct	3 ms	6492 KB	Output is correct
10	Correct	3 ms	6488 KB	Output is correct
11	Correct	2 ms	6492 KB	Output is correct
12	Correct	3 ms	6492 KB	Output is correct
13	Correct	3 ms	6492 KB	Output is correct
14	Correct	3 ms	6488 KB	Output is correct
15	Correct	3 ms	6492 KB	Output is correct
16	Correct	3 ms	6488 KB	Output is correct
17	Correct	3 ms	6740 KB	Output is correct
18	Correct	3 ms	6492 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	6484 KB	Output is correct
2	Correct	3 ms	6488 KB	Output is correct
3	Correct	3 ms	6492 KB	Output is correct
4	Correct	3 ms	6492 KB	Output is correct
5	Correct	3 ms	6748 KB	Output is correct
6	Correct	3 ms	6492 KB	Output is correct
7	Correct	3 ms	6484 KB	Output is correct
8	Correct	4 ms	6488 KB	Output is correct
9	Correct	3 ms	6492 KB	Output is correct
10	Correct	3 ms	6488 KB	Output is correct
11	Correct	2 ms	6492 KB	Output is correct
12	Correct	3 ms	6492 KB	Output is correct
13	Correct	3 ms	6492 KB	Output is correct
14	Correct	3 ms	6488 KB	Output is correct
15	Correct	3 ms	6492 KB	Output is correct
16	Correct	3 ms	6488 KB	Output is correct
17	Correct	3 ms	6740 KB	Output is correct
18	Correct	3 ms	6492 KB	Output is correct
19	Correct	4 ms	6748 KB	Output is correct
20	Correct	4 ms	6748 KB	Output is correct
21	Correct	4 ms	6824 KB	Output is correct
22	Correct	4 ms	6752 KB	Output is correct
23	Correct	3 ms	6752 KB	Output is correct
24	Correct	4 ms	7000 KB	Output is correct
25	Correct	3 ms	6744 KB	Output is correct
26	Correct	4 ms	6748 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	384 ms	29952 KB	Output is correct
2	Correct	396 ms	29532 KB	Output is correct
3	Correct	413 ms	29532 KB	Output is correct
4	Correct	366 ms	29748 KB	Output is correct
5	Correct	155 ms	19392 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	97 ms	16984 KB	Output is correct
2	Correct	96 ms	16980 KB	Output is correct
3	Correct	114 ms	17096 KB	Output is correct
4	Correct	45 ms	12376 KB	Output is correct
5	Correct	3 ms	6492 KB	Output is correct
6	Correct	49 ms	12280 KB	Output is correct
7	Correct	76 ms	15472 KB	Output is correct

Subtask #6
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	328 ms	27476 KB	Output is correct
2	Correct	253 ms	27984 KB	Output is correct
3	Correct	715 ms	48468 KB	Output is correct
4	Correct	197 ms	28752 KB	Output is correct
5	Correct	154 ms	27004 KB	Output is correct
6	Correct	289 ms	46044 KB	Output is correct
7	Correct	294 ms	46416 KB	Output is correct
8	Correct	193 ms	27476 KB	Output is correct

Subtask #7
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	6484 KB	Output is correct
2	Correct	3 ms	6488 KB	Output is correct
3	Correct	3 ms	6492 KB	Output is correct
4	Correct	3 ms	6492 KB	Output is correct
5	Correct	3 ms	6748 KB	Output is correct
6	Correct	3 ms	6492 KB	Output is correct
7	Correct	3 ms	6484 KB	Output is correct
8	Correct	4 ms	6488 KB	Output is correct
9	Correct	3 ms	6492 KB	Output is correct
10	Correct	3 ms	6488 KB	Output is correct
11	Correct	2 ms	6492 KB	Output is correct
12	Correct	3 ms	6492 KB	Output is correct
13	Correct	3 ms	6492 KB	Output is correct
14	Correct	3 ms	6488 KB	Output is correct
15	Correct	3 ms	6492 KB	Output is correct
16	Correct	3 ms	6488 KB	Output is correct
17	Correct	3 ms	6740 KB	Output is correct
18	Correct	3 ms	6492 KB	Output is correct
19	Correct	4 ms	6748 KB	Output is correct
20	Correct	4 ms	6748 KB	Output is correct
21	Correct	4 ms	6824 KB	Output is correct
22	Correct	4 ms	6752 KB	Output is correct
23	Correct	3 ms	6752 KB	Output is correct
24	Correct	4 ms	7000 KB	Output is correct
25	Correct	3 ms	6744 KB	Output is correct
26	Correct	4 ms	6748 KB	Output is correct
27	Correct	384 ms	29952 KB	Output is correct
28	Correct	396 ms	29532 KB	Output is correct
29	Correct	413 ms	29532 KB	Output is correct
30	Correct	366 ms	29748 KB	Output is correct
31	Correct	155 ms	19392 KB	Output is correct
32	Correct	97 ms	16984 KB	Output is correct
33	Correct	96 ms	16980 KB	Output is correct
34	Correct	114 ms	17096 KB	Output is correct
35	Correct	45 ms	12376 KB	Output is correct
36	Correct	3 ms	6492 KB	Output is correct
37	Correct	49 ms	12280 KB	Output is correct
38	Correct	76 ms	15472 KB	Output is correct
39	Correct	328 ms	27476 KB	Output is correct
40	Correct	253 ms	27984 KB	Output is correct
41	Correct	715 ms	48468 KB	Output is correct
42	Correct	197 ms	28752 KB	Output is correct
43	Correct	154 ms	27004 KB	Output is correct
44	Correct	289 ms	46044 KB	Output is correct
45	Correct	294 ms	46416 KB	Output is correct
46	Correct	193 ms	27476 KB	Output is correct
47	Correct	235 ms	27856 KB	Output is correct
48	Correct	211 ms	27744 KB	Output is correct
49	Correct	703 ms	48340 KB	Output is correct
50	Correct	196 ms	28984 KB	Output is correct
51	Correct	176 ms	23212 KB	Output is correct
52	Correct	246 ms	29008 KB	Output is correct
53	Correct	303 ms	47952 KB	Output is correct
54	Correct	307 ms	48820 KB	Output is correct
55	Correct	382 ms	42376 KB	Output is correct

Submission #911115

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 13.0 / 13.0

Subtask #4 10.0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 17.0 / 17.0

Subtask #7 25.0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
13.0 / 13.0

Subtask #4
10.0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
17.0 / 17.0

Subtask #7
25.0 / 25.0