Submission #617169

#	Time	Username	Problem	Language	Result	Execution time	Memory
617169		FatihSolak	Global Warming (CEOI18_glo)	C++17	100 / 100	707 ms	32152 KiB

glo

#include <bits/stdc++.h>
#define N 200005
using namespace std;
int t[N];
struct SegTree{
	vector<int> t;
	int n;
	SegTree(int sz){
		n = sz + 5;
		t.assign(4*n,0);
	}
	void clear(){
		t.assign(4*n,0);
	}
	void upd(int v,int tl,int tr,int pos,int val){
		if(tl == tr){
			t[v] = max(t[v],val);
			return;
		}
		int tm = (tl + tr)/2;
		if(pos <= tm)
			upd(v*2,tl,tm,pos,val);
		else upd(v*2+1,tm+1,tr,pos,val);
		t[v] = max(t[v*2],t[v*2+1]);
	}
	int get(int v,int tl,int tr,int l,int r){
		if(tr < l || r < tl)
			return 0;
		if(l <= tl && tr <= r){
			return t[v];
		}
		int tm = (tl + tr)/2;
		return max(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
	}
	void upd(int pos,int val){
		upd(1,1,n,pos,val);
	}
	int get(int l,int r){
		return get(1,1,n,l,r);
	}
};
pair<int,int> sufquery[N];
pair<int,int> prequery[N];
int val[N][3];
void solve(){
	int n,x;
	cin >> n >> x;
	int best = 0;
	vector<pair<int,int>> compress;
	for(int i = 1;i<=n;i++){
		cin >> t[i];
		compress.push_back({t[i],i});
		compress.push_back({t[i]+x,i+n});
		compress.push_back({t[i]-x,i+2*n});
	}
	sort(compress.begin(),compress.end());
	int sz = compress.size();
	int cnt = 0;
	for(int i = 0;i<sz;i++){
		if(i == 0 || compress[i].first != compress[i-1].first)
			cnt++;
		int x = compress[i].second;
		int y = 0;
		while(x > n){
			x -= n;
			y++;
		}
		val[x][y] = cnt+1;
	}
	SegTree tpre(sz);
	SegTree tsuf(sz);
	for(int i = 1;i<=n;i++){
		int num = val[i][2];
		tpre.upd(num,tpre.get(1,num-1)+1);
		best = max(best,tpre.get(1,sz));
		sufquery[i+1] = {tpre.get(num,num),num};
	}
	for(int i = n;i>=1;i--){
		int num = val[i][1];
		tsuf.upd(num,tsuf.get(num+1,sz)+1);
		best = max(best,tsuf.get(1,sz));
		prequery[i-1] = {tsuf.get(num,num),num};
	}
	tpre.clear();
	tsuf.clear();
	for(int i = 1;i<=n;i++){
		int num = val[i][0];
		tpre.upd(num,tpre.get(1,num-1)+1);
		best = max(best,prequery[i].first + tpre.get(1,prequery[i].second-1));
	}
	for(int i = n;i>=1;i--){
		int num = val[i][0];
		tsuf.upd(num,tsuf.get(num+1,sz)+1);
		best = max(best,sufquery[i].first + tsuf.get(sufquery[i].second+1,sz));
	}
	cout << best;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	#ifdef Local
		freopen("in.txt","r",stdin);
		freopen("out.txt","w",stdout);
	#endif
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	#ifdef Local
		cout << endl << fixed << setprecision(2) << 1000.0*clock()/CLOCKS_PER_SEC << " milliseconds";
	#endif
}

• 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