Submission #536256

#	Time	Username	Problem	Language	Result	Execution time	Memory
536256		getac	Financial Report (JOI21_financial)	C++14	100 / 100	470 ms	23848 KiB

Main

//InTheNameOfGOD
//PRS;)
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define rep(i, l, r) for(ll i = ll(l); i < ll(r); ++i)
#define per(i, l, r) for(ll i = ll(r) - 1; i >= ll(l); --i)
#define Fast cin.tie(0) -> sync_with_stdio(0);
#define X first
#define Y second
typedef long long ll;
using namespace std;
typedef pair<int, int> pi;
constexpr int xn = 3e5 + 5;
int a[xn], ans, sz = 1;
vector<int> v1;
inline int get(int l, int r)
{
	int ret = 0;
	l += sz, r += sz + 1;
	while(l < r)
	{
		if(l & 1) ret = max(ret, v1[l++]);
		if(r & 1) ret = max(ret, v1[--r]);
		l >>= 1, r >>= 1;
	}
	return ret;
}
inline void upd(int p, int v)
{
	ans = max(ans, v), v1[p += sz] = v, p >>= 1;
	while(p) v1[p] = max(v1[p << 1 | 0], v1[p << 1 | 1]), p >>= 1;
}
int main()
{
	Fast
	int n, d;
	cin >> n >> d;
	rep(i, 0, n) cin >> a[i];
	vector<int> v2;
	rep(i, 0, n) v2.push_back(a[i]);
	v2.push_back(-1), sort(v2.begin(), v2.end()), v2.erase(unique(v2.begin(), v2.end()), v2.end());
	rep(i, 0, n) a[i] = lower_bound(v2.begin(), v2.end(), a[i]) - v2.begin();
	int prs = v2.size();
	while(sz < prs) sz <<= 1;
	int t = sz << 1;
	while(t--) v1.push_back(0);
	set<pi> s1, s2;
	rep(i, 0, n)
	{
		upd(a[i], max(get(0, a[i] - 1) + 1, get(a[i], a[i]))), s1.insert({a[i], i});
		if(i < d) continue;
        s1.erase({a[i - d], i - d}), s2.insert({a[i - d], i - d});
        while(!s2.empty() && s2.begin() -> X < s1.begin() -> X)
			upd(s2.begin() -> X, 0), s2.erase(s2.begin());
	}
	cout << ans << '\n';
}

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