Submission #1307768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307768		kevins	Global Warming (CEOI18_glo)	C++20	10 / 100	198 ms	28596 KiB

glo

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

struct node{
	//range max pt update segtree
	ll s, e, m;
	ll val;
	node *left, *right;

	node(ll _s, ll _e){
		s = _s; e = _e; m = (s+e)/2;
		val = 0;
		left = right = nullptr;
		if (s != e){
			left = new node(s, m);
			right = new node(m+1, e);
		}
	}

	void upd(ll f, ll v){
		if (s == e){
		    val = v;
		    return;
		}
		if (f <= m) left->upd(f, v);
		else right->upd(f, v);
		val = max(left->val, right->val);
	}

	ll qry(ll l, ll r){
		if (s == l && e == r) return val;
		if (r <= m) return left->qry(l, r);
		else if (l > m) return right->qry(l, r);
		else return max(left->qry(l, m), right->qry(m+1, r));
	}
};

int main(){
	ll n, x;
	cin >> n >> x;
	
	if (x != 0) return 69;


	vector <ll> a(n);
	for (ll i = 0; i < n; ++i){
	    cin >> a[i];
	}


	vector <ll> dis = a;
	sort(dis.begin(), dis.end());
	dis.erase(unique(dis.begin(), dis.end()), dis.end());

	auto compress = [&](ll val){
		return lower_bound(dis.begin(), dis.end(), val) - dis.begin();
	};

	node* root = new node(0, n); //tree[i]: max len of lis ending at a[i]

	for (ll i = 0; i < n; ++i){
	    a[i] = compress(a[i]);
	}

	root->upd(a[0], 1); //lis of first element is 0

	for (ll i = 1; i < n; ++i){
		ll optimum;
		if (a[i]-1 < 0) optimum = 0;
		else optimum = root->qry(0, a[i]-1); //maximum of lis from all elements before it
		root->upd(a[i], optimum+1);
	}

	cout << root->qry(0, dis.size()-1) << "\n";
}

• 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