Submission #1273042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273042		nthvn	Global Warming (CEOI18_glo)	C++20	100 / 100	78 ms	6116 KiB

glo

#include "bits/stdc++.h"
using namespace std;

#define fi first
#define se second
#define pii pair<int,int> 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long
const int N =2e5+5;
int n, X;
int a[N], pos[N], posX[N];
int dp[N][2];
struct BIT{
	int bit[N];
	void update(int i, int x){
		for(;i<=n;i+=i&-i) bit[i] = max(bit[i],x);
	}
	int get(int i){
		int ans =0;
		for(;i;i-=i&-i) ans = max(ans,bit[i]);
		return ans;
	}
}bit[2];
void precalc(){
	vector<int> v; 
	for(int i=1;i<=n;i++) v.pb(a[i]);
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	for(int i=1;i<=n;i++){
		pos[i] = lower_bound(all(v),a[i]) - v.begin()+1;
		posX[i] = lower_bound(all(v), a[i]+X) - v.begin()+1;
	}
}

signed main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);
	if(fopen("TASK.INP", "r")){
		freopen("TASK.INP", "r", stdin);
		freopen("TASK.OUT", "w", stdout);
	}
	cin>>n>>X;
	for(int i=1;i<=n;i++) cin>>a[i];
	precalc();
	for(int i=1;i<=n;i++){
		dp[i][0] = bit[0].get(pos[i]-1)+1;
		dp[i][1] = max(bit[1].get(pos[i]-1), bit[0].get(posX[i]-1)) + 1;
		bit[0].update(pos[i], dp[i][0]);
		bit[1].update(pos[i], dp[i][1]);
	}
	cout<<*max_element(&dp[0][0], &dp[n][1]+1);
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:41:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |                 freopen("TASK.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:42:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |                 freopen("TASK.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