Submission #940102

#	Time	Username	Problem	Language	Result	Execution time	Memory
940102		viwlesxq	Global Warming (CEOI18_glo)	C++17	55 / 100	1134 ms	219676 KiB

glo

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
	return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
	return a < b ? (a = b) == b : false;
}

struct PST {
    int n, sz, cnt;
    vector<int> L, R, root, t, a;
    void construct(int n, vector<int> arr) {
        this -> n = n;
        a = arr, sz = 0, cnt = 1;
        L.assign(30 * n, 0), R.assign(30 * n, 0);
        root.assign(30 * n, 0), t.assign(30 * n, 0);
        root[1] = build(1, n);
    }
    int build(int tl, int tr) {
        int v = ++sz;
        if (tl == tr) {
            t[v] = a[tl];
            return v;
        }
        int tm = (tl + tr) >> 1;
        L[v] = build(tl, tm);
        R[v] = build(tm + 1, tr);
        t[v] = max(t[L[v]], t[R[v]]);
        return v;
    }
    int upd(int v, int tl, int tr, int i, int x) {
        int nv = ++sz;
        L[nv] = L[v];
        R[nv] = R[v];
        if (tl == tr) {
            t[nv] = x;
            return nv;
        }
        int tm = (tl + tr) >> 1;
        if (i <= tm) {
            L[nv] = upd(L[nv], tl, tm, i, x);
        } else {
            R[nv] = upd(R[nv], tm + 1, tr, i, x);
        }
        t[nv] = max(t[L[nv]], t[R[nv]]);
        return nv;
    } void upd(int id, int i, int x) {
        root[id] = upd(root[id], 1, n, i, x);
    }
    int get(int v, int tl, int tr, int l, int r) {
        if (tl > r || tr < l) {
            return 0ll;
        }
        if (tl >= l && tr <= r) {
            return t[v];
        }
        int tm = (tl + tr) >> 1;
        return max(get(L[v], tl, tm, l, r), get(R[v], tm + 1, tr, l, r));
    } int get(int id, int l) {
		if (l > n) return 0ll;
        return get(root[id], 1, n, l, n);
    }
    void copy(int id) {
        root[++cnt] = root[id];
    }
};

struct segtree {
	int n;
	vector<int> t;
	void construct(int n) {
		this -> n = n;
		t.assign(4 * n + 4, 0);
	}
	void upd(int v, int tl, int tr, int i, int delta) {
		if (tl == tr) {
			t[v] = delta;
			return;
		}
		int tm = (tl + tr) / 2;
		if (tm >= i) upd(2 * v, tl, tm, i, delta);
		else upd(2 * v + 1, tm + 1, tr, i, delta);
		t[v] = max(t[2 * v], t[2 * v + 1]);
	} void upd(int i, int delta) {
		upd(1, 1, n, i, delta);
	}
	int get(int v, int tl, int tr, int l, int r) {
		if (tl > r || tr < l) return 0ll;
		if (tl >= l && tr <= r) return t[v];
		int tm = (tl + tr) / 2;
		return max(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
	} int get(int l, int r) {
		if (l > r) return 0ll;
		return get(1, 1, n, l, r);
	}
};

PST pst;
segtree t;
map<int, int> mp;

void compress(vector<int> a, int x) {
	vector<int> v;
	for (int i = 0; i < size(a); ++i) {
		if (!mp.count(a[i])) v.push_back(a[i]), mp[a[i]];
		if (!mp.count(a[i] - x + 1)) v.push_back(a[i] - x + 1), mp[a[i] - x + 1];
	}
	sort(all(v));
	vector<int> constructor;
	for (int i = 0; i < size(v); ++i) {
		mp[v[i]] = i + 1;
		constructor.push_back(0);
	}
	constructor.push_back(0);
	pst.construct(size(v), constructor);
	t.construct(size(v));
}

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, x; cin >> n >> x;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	compress(a, x);
	for (int i = n - 1, idx = 2; i >= 0; --i, ++idx) {
		pst.copy(idx - 1);
		int dp = pst.get(idx, mp[a[i]] + 1) + 1;
		pst.upd(idx, mp[a[i]], dp);
	}
	int res = 0;
	for (int i = 0, idx = n; i < n; ++i, --idx) {
		int dp = t.get(1, mp[a[i]] - 1) + 1;
		t.upd(mp[a[i]], dp);
		chmax(res, dp + pst.get(idx, mp[a[i] - x + 1]));
	}
	cout << res;
}

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