Submission #1256696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256696		_filya_	Global Warming (CEOI18_glo)	C++20	100 / 100	815 ms	120956 KiB

glo

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

struct segtree {

	vector<ll> tree;
	int size;

	void init(int n) {
		size = 1;
		while (size < n)
			size *= 2;
		tree.assign(2 * size - 1, 0);
	}

	void build(vector<int>& a, int x, int lx, int rx) {
		if (rx - lx == 1) {
			if (lx < a.size())
				tree[x] = a[lx];
		}
		else {
			int m = (lx + rx) / 2;
			build(a, 2 * x + 1, lx, m);
			build(a, 2 * x + 2, m, rx);
			tree[x] = max(tree[2 * x + 1], tree[2 * x + 2]);
		}
	}

	void build(vector<int>& a) {
		init(a.size());
		build(a, 0, 0, size);
	}

	void set(int i, int v, int x, int lx, int rx) {
		if (rx - lx == 1) {
			tree[x] = v;
			return;
		}
		int m = (lx + rx) / 2;
		if (i < m) {
			set(i, v, 2 * x + 1, lx, m);
		}
		else {
			set(i, v, 2 * x + 2, m, rx);
		}
		tree[x] = max(tree[2 * x + 1], tree[2 * x + 2]);
	}

	void set(int i, int v) {
		set(i, v, 0, 0, size);
	}

	ll query(int l, int r, int x, int lx, int rx) {
		if (l >= rx || r <= lx) {
			return 0;
		}
		if (lx >= l && rx <= r) {
			return tree[x];
		}
		int m = (lx + rx) / 2;
		ll mi1 = query(l, r, 2 * x + 1, lx, m);
		ll mi2 = query(l, r, 2 * x + 2, m, rx);
		return max(mi1, mi2);
	}

	ll query(int l, int r) {
		return query(l, r, 0, 0, size);
	}
};

pair<map<ll, ll>, map<ll, ll>> compress(set<ll>& a) {
    int n = a.size();
    map<ll, ll> mp;
    map<ll, ll> res;
    int k = 1;
    for (auto it : a) {
        mp[it] = k;
        res[k++] = it;
    }
    return {mp, res};
}

vector<ll> find_lises(vector<ll>& a) {
    int n = a.size();
    segtree dp;
    dp.init(2 * n + 10);
    vector<ll> res(n);
    for (int i = 0; i < n; i++) {
        ll q = dp.query(0, a[i]);
        res[i] = q + 1;
        dp.set(a[i], max(q + 1, dp.query(a[i], a[i] + 1)));
    }
    return res;
}

int main()
{
// 	ifstream cin("input.txt");
//     ofstream cout("output.txt");
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	ll n, d; cin >> n >> d;
    vector<ll> a(n, 0);
    set<ll> c;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        c.insert(a[i]);
        c.insert(a[i] + d);
    }
    auto [mp_to, mp_from] = compress(c);
    for (auto& u : a) u = mp_to[u];
    vector<ll> dp1 = find_lises(a);
    for (auto& u : a) u = c.size() + 1 - u;
    reverse(a.begin(), a.end());
    vector<ll> dp2 = find_lises(a);
    reverse(dp2.begin(), dp2.end());
    for (auto& u : a) u = c.size() + 1 - u;
    reverse(a.begin(), a.end());
    segtree dp;
    dp.init(c.size() + 10);
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ll bnd = mp_to[mp_from[a[i]] + d];
        ans = max(ans, dp.query(0, bnd) + dp2[i]);
        dp.set(a[i], max(dp.query(a[i], a[i] + 1), dp1[i]));
    }
    cout << ans << '\n';
}

• 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