Submission #737663

#	Time	Username	Problem	Language	Result	Execution time	Memory
737663		bane	Global Warming (CEOI18_glo)	C++17	100 / 100	578 ms	118276 KiB

glo

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

const int maxN = (int)4e6;
int x,n,much = 0;

unordered_map<int,int>compress;

class SegmentTree{
	public:
	int tree[maxN * 3];
	inline void upd(int pos, int val, int l = 1, int r = much, int k = 1){
		if (l == r){
			tree[k] = max(tree[k], val);
			return;
		}
		int md = (l + r) >> 1;
		if (pos <= md)upd(pos,val,l,md,k*2);
		else upd(pos,val,md+1,r,k*2+1);
		tree[k] = max(tree[k * 2], tree[k * 2 + 1]);
	}
	
	inline int query(int a, int b, int l = 1, int r = much , int k = 1){
		if (l >= a && r <= b)return tree[k];
		if (l > b || r < a || a > b || a > much || b > much)return 0;
		return max(query(a,b,l,(l+r)/2,k*2), query(a,b,(l+r)/2+1,r,k*2+1));
	}
};

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> x;
	vector<int>a(n), b;
	for (int i = 0; i < n; i++){
		cin >> a[i];
		b.push_back(a[i]);
		b.push_back(a[i] - x);
	}
	sort(b.begin(), b.end());
	for (int i = 0; i < (int)b.size(); i++){
		if (!i || b[i] != b[i - 1])compress[b[i]] = ++much;
	}
	int dpLeft[n], dpRight[n], maxima = 0;
	SegmentTree L, R;
	for (int i = n - 1; i>=0; i--){
		dpRight[i] = R.query(compress[a[i]-x] + 1, much) + 1;
		R.upd(compress[a[i]], R.query(compress[a[i]] + 1, much) + 1);
	}
	for (int i = 0 ; i < n; i++){
		dpLeft[i] = L.query(1, compress[a[i]] - 1) + 1;
		L.upd(compress[a[i]], dpLeft[i]);
	}
	for (int i = 0 ; i < n; i++){
		maxima = max(maxima, dpLeft[i] + dpRight[i] - 1);
	}
	cout<<maxima<<'\n';
	return 0;
}

• 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