Submission #1179993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179993		PieArmy	Global Warming (CEOI18_glo)	C++20	100 / 100	482 ms	34080 KiB

glo

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;

struct Seg{
	int n;
	vector<int>tree;
	void init(int N){
		n=N;
		tree.resize(n<<2,0);
	}
	int l,r;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node]=max(tree[node],r);
			return;
		}
		const int mid=(left+right)>>1;
		if(l>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		tree[node]=max(tree[node*2],tree[node*2+1]);
	}
	void update(int tar,int val){
		l=tar;r=val;
		up();
	}
	int qu(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>=l&&right<=r)return tree[node];
		if(left>r||right<l)return 0;
		const int mid=(left+right)>>1;
		return max(qu(node*2,left,mid),qu(node*2+1,mid+1,right));
	}
	int query(int left,int right){
		l=left;r=right;
		if(r<0)return 0;
		return qu();
	}
};

int n,k;
int arr[200023];
Seg seg1,seg2;
int m;
map<int,int>mp;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>k;
	vector<int>v;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		v.pb(arr[i]);
		v.pb(arr[i]+k);
	}
	sort(v.begin(),v.end());
	for(int x:v){
		if(mp[x]==0){
			mp[x]=++m;
		}
	}
	seg1.init(m+1);
	seg2.init(m+1);
	for(int i=1;i<=n;i++){
		seg2.update(mp[arr[i]],max(seg2.query(0,mp[arr[i]]-1),seg1.query(0,mp[arr[i]+k]-1))+1);
		seg1.update(mp[arr[i]],seg1.query(0,mp[arr[i]]-1)+1);
	}
	cout<<seg2.query(0,m);
}

• 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