Submission #72890

#	Time	Username	Problem	Language	Result	Execution time	Memory
72890		zscoder	Global Warming (CEOI18_glo)	C++17	100 / 100	181 ms	6372 KiB

glo

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int a[222222];
int P[222222];
int S[222222];

struct Fenwick
{
	vi fen;
	int n;
	void init(int _n)
	{
		n=_n; fen.clear();
		fen.resize(n+1,0);
	}
	void update(int pos, int v)
	{
		pos++;
		for(;pos<=n;pos+=(pos&(-pos)))
		{
			fen[pos]=max(fen[pos],v);
		}
	}
	int get(int pos)
	{
		if(pos<0) return 0;
		pos++;
		int ans=0;
		for(;pos;pos-=(pos&(-pos)))
		{
			ans=max(ans,fen[pos]);
		}
		return ans;
	}
};

vi coord;
int id[222222];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, x; cin>>n>>x;
	for(int i=0;i<n;i++)
	{
		cin>>a[i]; coord.pb(a[i]);
	}
	sort(coord.begin(),coord.end()); coord.erase(unique(coord.begin(),coord.end()),coord.end());
	for(int i=0;i<n;i++)
	{
		id[i] = lower_bound(coord.begin(),coord.end(),a[i])-coord.begin();
	}
	Fenwick fen; fen.init(n+1);
	for(int i=0;i<n;i++)
	{
		P[i] = fen.get(id[i]-1)+1;
		fen.update(id[i],P[i]);
	}
	fen.init(n+1);
	for(int i=n-1;i>=0;i--)
	{
		S[i] = fen.get(n-id[i]-1)+1;
		fen.update(n-id[i],S[i]);
	}
	int ans=P[n-1];
	Fenwick fen2; fen2.init(n+1);
	for(int j=0;j<n;j++)
	{
		int lb = lower_bound(coord.begin(),coord.end(),a[j]+x)-coord.begin();
		ans=max(ans, S[j]+fen2.get(lb-1));
		fen2.update(id[j],P[j]);
	}
	cout<<ans<<'\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