Submission #1097156

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1097156	2024-10-06T10:14:35 Z	taimoitapcode1	Global Warming (CEOI18_glo)	C++14	10 / 100	292 ms	16212 KB

glo

#include <bits/stdc++.h>
using namespace std;


int n, k;

int a[1303207], cong[1303207];


int st[4 * 2 * 200005];

int dp[200005];

map<int, int> lab;

void ud(int id, int l, int r, int pos, int k){
	if(l > pos || r < pos) return;


	if(l == r){
		st[id] = k;
		return;
	}


	int mid = (l + r) >> 1;


	ud(id * 2, l, mid, pos, k);
	ud(id * 2 + 1, mid + 1, r, pos, k);

	st[id] = max(st[id * 2], st[id * 2 + 1]);
}


int get(int id, int l, int r, int L, int R){
	if(l > R || r < L) return 0;

	if(L <= l && r <= R) return st[id];


	int mid = (l + r) >> 1;

	return max(get(id * 2, l, mid, L, R), get(id * 2 + 1, mid + 1, r, L, R));
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);


	cin >> n >> k;

	for (int i = 1; i <= n; i++){
		cin >> a[i];
		lab[a[i]];
		lab[a[i] + k];
	}



	int cnt = 0;

	for (auto [x, y] : lab){
		lab[x] = ++cnt;
	}



	for (int i = 1; i <= n; i++){
		cong[i] = lab[a[i] + k];	
		a[i] = lab[a[i]];
	}


	int ans = 0;

	for (int i = 1; i <= n; i++){
		int tmp0 = get(1, 1, 2 * n, 1, a[i] - 1) + 1;

		int tmp1 = get(1, 1, 2 * n, 1, cong[i] - 1) + 1;

		if(a[i] > a[i - 1]) tmp1 = max(tmp1, dp[i - 1] + 1);


		ans = max({ans, tmp0, tmp1});

		dp[i] = tmp1;
		ud(1, 1, 2 * n, a[i], tmp0);
		dp[i] = tmp1;
	}


	cout << ans;
}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:63:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |  for (auto [x, y] : lab){
      |            ^

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	460 KB	Output is correct
11	Incorrect	1 ms	344 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	460 KB	Output is correct
11	Incorrect	1 ms	344 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	460 KB	Output is correct
11	Incorrect	1 ms	344 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	270 ms	15968 KB	Output is correct
2	Correct	271 ms	16208 KB	Output is correct
3	Correct	277 ms	16036 KB	Output is correct
4	Correct	292 ms	16212 KB	Output is correct
5	Correct	120 ms	9552 KB	Output is correct

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	63 ms	7104 KB	Output is correct
2	Correct	61 ms	7248 KB	Output is correct
3	Correct	63 ms	7128 KB	Output is correct
4	Incorrect	32 ms	4192 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #6

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	142 ms	12880 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	460 KB	Output is correct
11	Incorrect	1 ms	344 KB	Output isn't correct
12	Halted	0 ms	0 KB	-