Submission #518680

#	Time	Username	Problem	Language	Result	Execution time	Memory
518680		zhangjishen	Global Warming (CEOI18_glo)	C++98	100 / 100	128 ms	7860 KiB

glo

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

template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}
typedef long long ll;
const int MAXN = 2e5 + 10;

int n, x, a[MAXN], b[MAXN], t, d[MAXN], f[MAXN], g[MAXN];

// fenwick tree
struct BIT{
	int c[MAXN];
	void update(int i, int k){
		for(; i <= t; i += i & -i)
			chkmax(c[i], k);
	}
	int qry(int i){
		int ans = 0;
		for(; i; i -= i & -i)
			chkmax(ans, c[i]);
		return ans;
	}
}c1, c2;

int main(){
	// input
	scanf("%d %d", &n, &x);
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	// disc
	for(int i = 1; i <= n; i++)
		d[i] = a[i];
	sort(d + 1, d + 1 + n);
	t = unique(d + 1, d + 1 + n) - (d + 1);
	for(int i = 1; i <= n; i++)
		b[i] = lower_bound(d + 1, d + 1 + t, a[i]) - d;
	// dp
	for(int i = 1; i <= n; i++){
		// update f
		f[i] = c1.qry(b[i] - 1) + 1;	
		// update g
		chkmax(g[i], c2.qry(b[i] - 1) + 1);
		int m = lower_bound(d + 1, d + 1 + t, a[i] + x) - d;
		chkmax(g[i], c1.qry(m - 1) + 1);
		// update c1, c2 to [1, i]
		c1.update(b[i], f[i]);
		c2.update(b[i], g[i]);
	}
	int ans = 0;
	for(int i = 1; i <= n; i++)
		chkmax(ans, g[i]);
	printf("%d\n", ans);
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d %d", &n, &x);
      |  ~~~~~^~~~~~~~~~~~~~~~~
glo.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~

• 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