Submission #720866

#	Time	Username	Problem	Language	Result	Execution time	Memory
720866		WonderfulWhale	Global Warming (CEOI18_glo)	C++17	100 / 100	355 ms	15356 KiB

glo

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

#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

struct SegTree {
	const static int T = 1<<18;
	int t[2*T];
	void update(int x, int val) {
		x+=T;
		t[x] = max(t[x], val);
		x/=2;
		while(x) {
			t[x] = max(t[2*x], t[2*x+1]);
			x/=2;
		}
	}
	int query(int l, int r) {
		l+=T;
		r+=T;
		int ret = max(t[l], t[r]);
		while(l/2!=r/2) {
			if(l%2==0) ret = max(ret, t[l+1]);
			if(r%2==1) ret = max(ret, t[r-1]);
			l/=2;
			r/=2;
		}
		return ret;
	}
} seg1, seg2;

map<int, int> M;

int tab[200009];

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, d;
	cin >> n >> d;
	vector<int> v;
	for(int i=0;i<n;i++) {
		cin >> tab[i];
		v.pb(tab[i]);
	}
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	for(int i=0;i<sz(v);i++) {
		M[v[i]] = i;
	}
	for(int i=0;i<n;i++) {
		int pos = M[tab[i]];
		auto it1 = M.upper_bound(tab[i]-1);
		auto it2 = M.upper_bound(tab[i]+d-1);
		if(it2!=M.begin()) {
			it2--;
			seg2.update(pos, 1+seg1.query(0, it2->nd));
		} else {
			seg2.update(pos, 1);
		}
		if(it1!=M.begin()) {
			it1--;
			seg2.update(pos, 1+seg2.query(0, it1->nd));
			seg1.update(pos, 1+seg1.query(0, it1->nd));
		} else {
			seg2.update(pos, 1);
			seg1.update(pos, 1);
		}
	}
	cout << seg2.query(0, n) << "\n";
}

• 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