Submission #1269791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269791		herominhsteve	Global Warming (CEOI18_glo)	C++20	100 / 100	109 ms	6060 KiB

glo

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "CEOI18_glo"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

template<typename T>
struct FenwickTree{
	int n;
	vector<T> bit;
	FenwickTree(int N=0){
		n=N;
		if (n>0){
			bit.resize(n+1,0);
		}
	}
	void update(int node,T val){
		while (node<=n){
			maximize(bit[node],val);
			node += (node & -node);
		}
	}
	T getVal(int node){
		T res=0;
		while (node>0){
			maximize(res,bit[node]);
			node -= (node & -node);
		}
		return res;
	}
};

int n,m,D;
vector<int> a;
vector<int> compressAll;

void init(){
	cin>>n>>D;
	a.resize(n);
	for (int &x:a){
		cin>>x;
		compressAll.push_back(x);
		compressAll.push_back(x+D);
	}
	sort(allof(compressAll));
	compressAll.resize(unique(allof(compressAll))-compressAll.begin());
	m = compressAll.size();
}

int getID(int x){
	return lower_bound(allof(compressAll),x) - compressAll.begin() + 1;
}

void sol(){
	FenwickTree<int> bitNor(m);
	FenwickTree<int> bitUp(m);
	int res=1;
	for (int x : a){
		int ID = getID(x);
		int curNormal = bitNor.getVal(ID-1) + 1;
		int curUp = bitUp.getVal(ID-1) + 1;
		int addX = getID(x+D);
		if (addX>=1) maximize(curUp,bitNor.getVal(addX-1) + 1);
		bitNor.update(ID,curNormal);
		bitUp.update(ID,curUp);
		maximize(res,max(curNormal,curUp));
	}
	cout<<res;
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

glo.cpp: In function 'void setup()':
glo.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• 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