Submission #1245336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245336		NikoBaotic	Financial Report (JOI21_financial)	C++20	60 / 100	4094 ms	95604 KiB

Main

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)

const int N = 3e5 + 10;
const int off = 1 << 19;

pii tr[off * 4];

void update(int node, int val) {
	node += off;

	tr[node] = {val, node - off};

	while (node /= 2) {
		tr[node] = max(tr[node * 2], tr[node * 2 + 1]);
	}
}

pii query(int l, int r, int node = 1, int x = 0, int y = off - 1) {
	if (l > y or x > r) return {-INT_MAX, 0};
	if (l <= x and y <= r) return tr[node];

	return max(query(l, r, node * 2, x, (x + y) / 2), query(l, r, node * 2 + 1, (x + y) / 2 + 1, y));
}

pii tr2[off * 4];
ll lazy[off * 4];
ll odz[off * 4];

void prop(int node, int x, int y) {
	if (tr2[node].F == INT_MAX) {
		odz[node] = 0;
		lazy[node] = 0;	
	}

	if (lazy[node] != 0) tr2[node] = {lazy[node], x};
	else tr2[node].F += odz[node];

	if (x != y) {
		if (odz[node]) {
			prop(node * 2, x, (x + y) / 2);
			prop(node * 2 + 1, (x + y) / 2 + 1, y);

			odz[node * 2] += odz[node];
			odz[node * 2 + 1] += odz[node];
		} else if (lazy[node]) {
			odz[node * 2] = 0;
			odz[node * 2 + 1] = 0;

			lazy[node * 2] = lazy[node];
			lazy[node * 2 + 1] = lazy[node];
		}
	}

	odz[node] = 0;
	lazy[node] = 0;
}

void ov(int l, int r, int val, int node = 1, int x = 0, int y = off - 1) {
	prop(node, x, y);

	if (l > y or x > r) return;
	if (l <= x and y <= r) {
		lazy[node] = val;
		prop(node, x, y);

		if (x == y) {
			tr2[node].F = val;
			tr2[node].S = x;
		}

		return;
	}

	ov(l, r, val, node * 2, x, (x + y) / 2);
	ov(l, r, val, node * 2 + 1, (x + y) / 2 + 1, y);

	tr2[node] = min(tr2[node * 2], tr2[node * 2 + 1]);
}

void add(int l, int r, int delta, int node = 1, int x = 0, int y = off - 1) {
	prop(node, x, y);

	if (l > y or x > r) return;
	if (l <= x and y <= r) {
		odz[node] = delta;
		prop(node, x, y);
		return;
	}

	add(l, r, delta, node * 2, x, (x + y) / 2);
	add(l, r, delta, node * 2 + 1, (x + y) / 2 + 1, y);

	tr2[node] = min(tr2[node * 2], tr2[node * 2 + 1]);
}

pii find(int l, int r, int node = 1, int x = 0, int y = off - 1) {
	prop(node, x, y);

	if (l > y or x > r) return {INT_MAX, 0};
	if (l <= x and y <= r) return tr2[node];

	return min(find(l, r, node * 2, x, (x + y) / 2), find(l, r, node * 2 + 1, (x + y) / 2 + 1, y));
}

int n, d;
int a[N];
set<pii> s[N];

int main() {
	FIO;

	for (int i = 0; i < off * 4; i++) {
		tr2[i] = {INT_MAX, 0};
	}

	cin >> n >> d;

	set<int> se;
	map<int, int> conv;

	for (int i = 0; i < n; i++) {
		cin >> a[i];

		se.insert(a[i]);
	}

	int cur = 0;

	for (int x : se) {
		conv[x] = ++cur;
	}

	for (int i = 0; i < n; i++) {
		a[i] = conv[a[i]];
	}

	int ans = 0;

	for (int i = 0; i < n; i++) {
		add(1, n, -1);

		pii k = find(0, n);

		while (k.F < 0) {
			int val = k.S;

			update(val, 0);
			ov(val, val, INT_MAX);

			while (sz(s[val]) and prev(s[val].end())->S + d < i) {
				s[val].erase(prev(s[val].end()));
			}

			if (sz(s[val])) {
				auto iter = prev(s[val].end());

				update(val, iter->F);
				ov(val, val, iter->S + d - i);
			}

			k = find(1, n);
		}

		ov(a[i], n, d);

		int val = query(0, a[i] - 1).F + 1;

		if (query(a[i], a[i]).F <= val) {
			update(a[i], val);
			ov(a[i], a[i], d);
		} else {
			s[a[i]].insert({val, i});
		}
		
		if (i + d + 1 >= n) ans = max(ans, (int)query(1, n).F);
	}

	cout << ans << endl;

	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35