Submission #1097156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097156		taimoitapcode1	Global Warming (CEOI18_glo)	C++14	10 / 100	292 ms	16212 KiB

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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25