Submission #539785

#	Time	Username	Problem	Language	Result	Execution time	Memory
539785		rk42745417	Financial Report (JOI21_financial)	C++17	12 / 100	85 ms	9160 KiB

Main

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

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const ll LINF = ll(4e18) + ll(2e15);
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
static int LamyIsCute = []() {
	EmiliaMyWife
	return 48763;
}();

const int N = 3e5 + 25;
struct segtree {
	int n, arr[N << 1], tag[N];
	void init(int _n) { n = _n; }
	void upd(int p, int v) {
		arr[p] += v;
		if(p < n)
			tag[p] += v;
	}
	void pull(int p) {
		for(; p > 1; p >>= 1)
			arr[p >> 1] = max(arr[p], arr[p ^ 1]) + tag[p >> 1];
	}
	void edt(int l, int r, int v) {
		int tl = l + n, tr = r + n - 1;
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1)
				upd(l++, v);
			if(r & 1)
				upd(--r, v);
		}
		pull(tl);
		pull(tr);
	}
	int que() { return arr[1]; }
} tree;

signed main() {
	int n, d;
	cin >> n >> d;
	assert(d == 1);
	vector<int> arr(n);
	for(int &a : arr)
		cin >> a;
	tree.init(n);

	vector<int> l(n, -1);
	{
		stack<int, vector<int>> st;
		for(int i = 0; i < n; i++) {
			while(!st.empty() && arr[st.top()] < arr[i])
				st.pop();
			if(!st.empty())
				l[i] = st.top();
			st.push(i);
		}
	}
	for(int i = 0; i < n; i++)
		tree.edt(l[i] + 1, i + 1, 1);
	cout << tree.que() << '\n';
}

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