Submission #799902

#	Time	Username	Problem	Language	Result	Execution time	Memory
799902		ymm	Financial Report (JOI21_financial)	C++17	100 / 100	2472 ms	26836 KiB

Main

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int S = 1000;
const int N = 300'010+S;

struct sq_t {
	vector<int> arr, val;

	void init(int *a, int *b, int n) {
		vector<pii> vec;
		Loop (i,0,n)
			vec.push_back({a[i], b[i]});
		sort(vec.begin(), vec.end());
		vector<pii> vec2;
		Loop (i,0,n) {
			if (vec2.size() && vec2.back().second >= vec[i].second)
				continue;
			vec2.push_back(vec[i]);
		}
		for (auto x : vec2) {
			arr.push_back(x.first);
			val.push_back(x.second);
		}
	}
	int get(int x) {
		int i = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
		return i? val[i-1]: 0;
	}
} sq[N/S];

int arr[N], val[N];

int get_naive(int l, int r, int x)
{
	int ans = 0;
	Loop (i,l,r) {
		int dard = arr[i] < x? val[i]: 0;
		int marg = dard > ans? dard: ans;
		ans = marg;
	}
	return ans;
}

int get(int l, int r, int x)
{
	if (l/S == (r-1)/S)
		return get_naive(l, r, x);
	int ans = 0;
	int l2 = l%S? l+S-l%S: l;
	int r2 = r-r%S;
	ans = max(get_naive(l, l2, x), get_naive(r2, r, x));
	Loop (i,l2/S,r2/S)
		ans = max(ans, sq[i].get(x));
	return ans;
}

set<int> ok, not_ok;
int ql[N];

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, d;
	cin >> n >> d;
	vector<pii> vec;
	Loop (i,0,n) {
		cin >> arr[i];
		vec.push_back({arr[i], i});
	}
	sort(vec.begin(), vec.end());
	reverse(vec.begin(), vec.end());
	not_ok = {-1, n};
	Loop (i,-1,n+1)
		ok.insert(ok.end(), i);
	for (auto [_, i] : vec) {
		ql[i] = *--not_ok.lower_bound(i) + 1;
		auto it = ok.find(i);
		auto it0 = it; --it0;
		auto it1 = it; ++it1;
		ok.erase(it);
		//cerr << i << ' ' << *it0 << ' ' << *it1 << '\n';
		if (*it1 - *it0 - 1 < d)
			continue;
		auto itt = not_ok.insert(i);
		for (int x = i+1; x < *it1 && !not_ok.count(x); ++x)
			not_ok.insert(x);
		for (int x = i-1; x > *it0 && !not_ok.count(x); --x)
			not_ok.insert(x);
	}
	val[0] = 1;
	Loop (i,1,n) {
		if (i%S == 0)
			sq[i/S-1].init(arr+i-S, val+i-S, S);
		val[i] = get(ql[i], i, arr[i]) + 1;
	}
	int ans = 0;
	Loop (i,0,n)
		ans = max(ans, val[i]);
	cout << ans << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:89:8: warning: variable 'itt' set but not used [-Wunused-but-set-variable]
   89 |   auto itt = not_ok.insert(i);
      |        ^~~

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