Submission #314584

#	Time	Username	Problem	Language	Result	Execution time	Memory
314584		nafis_shifat	Global Warming (CEOI18_glo)	C++14	100 / 100	505 ms	12368 KiB

glo

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=6e5+5;
const int inf=1e9;
vector<int> v;
struct BIT1 {
	int bit[mxn] = {};
	void update(int p,int v) {
		for(;p<mxn;p+=p&-p) bit[p]=max(bit[p],v);
	}
    int query(int p,int r = 0) {
    	for(;p>0;p-=p&-p) r=max(r,bit[p]);
        return r;
    }
} inc,bt1;
struct BIT2 {
	int bit[mxn] = {};
	void update(int p,int v) {
		for(;p>0;p-=p&-p) bit[p]=max(bit[p],v);
	}
    int query(int p,int r = 0) {
    	for(;p<mxn;p+=p&-p) r=max(r,bit[p]);
        return r;
    }
} dc,bt2;

int get(int x) {
	return lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
}

int main() {
	int n,x;
	cin>>n>>x;	

	int a[n+1];
	for(int i = 1; i <= n; i++) {
		cin>>a[i];
		v.push_back(a[i]);
		v.push_back(a[i] - x);
		v.push_back(a[i] + x);
	}

	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	int dp1[mxn],dp2[mxn];

	int ans = 0;
	for(int i = 1; i <= n; i++) {
		int p = get(a[i]);
		int x = inc.query(p - 1);
		dp1[i] = x + 1;
		ans = max(ans,dp1[i]);
		inc.update(p,dp1[i]); 
	}

	for(int i = n; i > 0 ; i--) {
		int p = get(a[i]);
		int x = dc.query(p + 1);
		dp2[i] = x + 1;
		dc.update(p,dp2[i]); 
	}


	for(int i = 1; i <= n; i++) {
		int ind = get(a[i]);
		int v = bt1.query(ind - 1);
		ans = max(ans, v + dp2[i]);
		bt1.update(get(a[i] - x), dp1[i]);

	}

	for(int i = n; i >= 1; i--) {
		int ind = get(a[i]);
		int v = bt2.query(ind + 1);
		ans = max(ans, v + dp1[i]);
		bt1.update(get(a[i] + x), dp2[i]);

	}

	cout<<ans<<endl;

}

• 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