제출 #73468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73468		duckmoon99	Global Warming (CEOI18_glo)	C++14	100 / 100	1380 ms	26976 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
#define fbo find_by_order
#define ook order_of_key
#define INF 1e18
#define ret return

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

int treee[522222];
int treee1[522222];
int n;
ll x;

void upd(int h, int xx){
	for(;h <= 2*n; h+=(h&(-h))){
		treee[h]=max(treee[h],xx);
	}
}

int que(int v){
	int res = 0;
	while(v){
		res=max(res,treee[v]);
		v-=(v&(-v));
	}
	ret res;
}

void upd1(int h, int xx){
	for(;h <= 2*n; h+=(h&(-h))){
		treee1[h]=max(treee1[h],xx);
	}
}

int que1(int v){
	//cout << v << endl;
	int res = 0;
	while(v){
		res=max(res,treee1[v]);
		v-=(v&(-v));
	}
	ret res;
}

vi b;
map<int,int> id;
int a[222222],p[222222], s[222222];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> x;
    for(int i = 0; i < n; i++){
		cin >> a[i];
		b.pb(a[i]);
		b.pb(a[i]+x-1);
	}
	sort(b.begin(),b.end());
	for(int i = 0; i < 2*n; i++){
		id[b[i]]=i+1;
	}
	for(int i = 0; i < n; i++){
		p[i]=que(id[a[i]]-1)+1;
		upd(id[a[i]],p[i]);
	}
	b.clear();
	for(int i = 0; i < n; i++){
		b.pb(-id[a[i]]+2*n+1);
	}
	reverse(b.begin(),b.end());
	for(int i = 0; i < n; i++){
		//cout << b[i] << " ";
		s[n-i-1]=que1(b[i]-1)+1;
		upd1(b[i],s[n-i-1]);
	}
	int ans = p[n-1];
	memset(treee,0,sizeof(treee));
	for(int i = 0; i < n; i++){
		ans=max(que(id[a[i]+x-1])+s[i],ans);
		upd(id[a[i]],p[i]);
	}
	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