Submission #1126683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126683		TrieTr	Global Warming (CEOI18_glo)	C++20	0 / 100	118 ms	10560 KiB

glo

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

void local() {
    #define taskname ""
    if (fopen(taskname".inp", "r")) {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
}

#define ll long long
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

template<class X, class Y> bool mini(X &a, const Y &b) {return (a > b) ? a = b, true : false;}
template<class X, class Y> bool maxi(X &a, const Y &b) {return (a < b) ? a = b, true : false;}

const int N = 1e6 + 5;

int n, a[N], lim, x;

int node[N << 1];
void update(int i, int v) {
	for(node[i += lim] = v, i >>= 1; i; i >>= 1) {
		node[i] = max(node[i << 1], node[i << 1 | 1]);
	}
}
int get(int l, int r) {
	int res = 0;
	for(l += lim, r += lim + 1; l < r; l >>= 1, r >>= 1) {
		if(l & 1) maxi(res, node[l++]);
		if(r & 1) maxi(res, node[--r]);
	}
	return res;
}
int dp[N];
int main() {
    fastio; local();
    cin >> n >> x;
    vector<int> val;
    for(int i = 1; i <= n; i++) cin >> a[i];

    val.emplace_back(-2e9);
	for(int i = 1; i <= n; i++) val.emplace_back(a[i]);
    sort(val.begin(), val.end()); val.resize(unique(val.begin(), val.end()) - val.begin()); lim = val.size();
	auto Rank = [&](int x) {
		return lower_bound(val.begin(), val.end(), x) - val.begin();
	};
	for(int i = 1; i <= n; i++) a[i] = Rank(a[i]);
	int res = 0;
	for(int i = 1; i <= n; i++) {
		dp[i] = get(1, a[i]) + 1;
		update(a[i], dp[i]);
		maxi(res, dp[i]);
	}
	memset(node, 0, sizeof(node));
	for(int i = n; i > 0; i--) {
		dp[i] = get(1, a[i]) + 1;
		update(a[i], dp[i]);
		int p = Rank(a[i - 1] - x);
		maxi(res, dp[i - 1] + get(p, lim));
	}
	cout << res;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25