Submission #828521

#	Time	Username	Problem	Language	Result	Execution time	Memory
828521		shoryu386	Global Warming (CEOI18_glo)	C++17	100 / 100	619 ms	256452 KiB

glo

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

//#define int long long

struct node{
	int s, e, m;
	int v = 0;
	node *l = nullptr, *r = nullptr;
	
	node(int _s, int _e){
		s = _s, e = _e, m = (s+e)/2;
	}
	
	void deletefkfkfk(){
		if (l != nullptr) l->deletefkfkfk(), delete l;
		if (r != nullptr) r->deletefkfkfk(), delete r;
	}
	
	void make_l(){
		if (l == nullptr) l = new node(s, m);
	}
	
	void make_r(){
		if (r == nullptr) r = new node(m+1, e);
	}
	
	void update(int x, int y){
		if (s == e) {v = max(v, y); return;}
		
		if (x <= m) make_l(), l->update(x, y), v = max(v, l->v);
		else make_r(), r->update(x, y), v = max(v, r->v);
	}
	
	int query(int x, int y){
		//cout << s << ' ' << e << '\n';
		if (x <= s && e <= y) return v;
		
		if (y <= m) {
			if (l == nullptr) return 0;
			return l->query(x, y);
		}
		else if (x > m) {
			if (r == nullptr) return 0;
			return r->query(x, y);
		}
		else {
			if (l == nullptr && r == nullptr) return 0;
			if (l == nullptr) return r->query(m+1, y);
			if (r == nullptr) return l->query(x, m);
			return max(l->query(x, m), r->query(m+1, y));
		}
	}
};

main(){
	int n, bruh; cin >> n; cin >> bruh;
	
	int arr[n];
	for (int x = 0; x < n; x++) cin >> arr[x];

	node st2(0, 2000000000), st3(0, 2000000000);
	
	int plis[n];
	int slis[n];
	for (int x = n-1; x > -1; x--){
		slis[x] = st2.query(arr[x]+1, 2000000000)+1;
		st2.update(arr[x], slis[x]);
	}

	int ans = 0;
	for (int x = 0; x < n; x++){
		plis[x] = st3.query(0, arr[x]-1)+1;
		ans = max(ans, st3.query(0, arr[x] + bruh - 1) + slis[x]);
		st3.update(arr[x], plis[x]);
	}
	
	cout << ans;
}

Compilation message (stderr)

glo.cpp:56:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   56 | main(){
      | ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25