Submission #651174

#	Time	Username	Problem	Language	Result	Execution time	Memory
651174		ymm	Financial Report (JOI21_financial)	C++17	100 / 100	1443 ms	21288 KiB

Main

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

const int N = 300'010;
const int S = 512;
struct node {
	int pre = 0;
	int suf = 0;
	int mx = 0;
} seg[N*4];

void merge(int i, int b, int e)
{
	int len1 = (e-b)/2;
	int len2 = (e-b+1)/2;
	seg[i].pre = seg[2*i+1].pre == len1?
	             len1 + seg[2*i+2].pre:
	             seg[2*i+1].pre;
	seg[i].suf = seg[2*i+2].suf == len2?
	             len2 + seg[2*i+1].suf:
	             seg[2*i+2].suf;
	seg[i].mx = max({seg[2*i+1].mx, seg[2*i+2].mx,
	                 seg[2*i+1].suf + seg[2*i+2].pre});
}

void up_seg(int p, int i, int b, int e)
{
	if (e - b == 1) {
		seg[i] = {1, 1, 1};
		return;
	}
	if (p < (b+e)/2)
		up_seg(p, 2*i+1, b, (b+e)/2);
	else
		up_seg(p, 2*i+2, (b+e)/2, e);
	merge(i, b, e);
}

int get_seg(int d, int r, int i, int b, int e)
{
	if (r <= b || seg[i].mx < d)
		return 0;
	if (e-b == 1)
		return e;
	if ((b+e)/2 < r) {
		int tmp = get_seg(d, r, 2*i+2, (b+e)/2, e);
		if (tmp) return tmp;
	}
	if ((b+e)/2 <= r && seg[2*i+2].pre + seg[2*i+1].suf >= d)
		return (b+e)/2 + seg[2*i+2].pre;
	return get_seg(d, r, 2*i+1, b, (b+e)/2);
}

int dp[N], a[N];
int ql[N];
int n;

int get_mx(int l, int r, int x)
{
	int ans = 0;
	Loop (i,l,r)
		ans = ans < dp[i] && a[i] < x? dp[i]: ans;
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int d;
	cin >> n >> d;
	vector<pii> srt;
	vector<pii> s;
	Loop (i,0,n) {
		cin >> a[i];
		srt.push_back({a[i], i});
		s.push_back({a[i], i});
	}
	sort(s.begin(), s.end());
	sort(srt.begin(), srt.end(), [](pii x, pii y){
		return    x.first > y.first
		       || (x.first == y.first && x.second < y.second);
	});
	for (auto [x, i] : srt) {
		ql[i] = get_seg(d, i, 0, 0, n);
		up_seg(i, 0, 0, n);
	}
	assert(clock() <= CLOCKS_PER_SEC);
	for (int l = 0; l < n; l += S) {
		int r = min(l + S, n);
		vector<int> vec;
		Loop (i,l,r) {
			dp[i] = max(dp[i], get_mx(max(ql[i], l), i, a[i]));
			dp[i] += 1;
			vec.push_back(a[i]);
		}
		sort(vec.begin(), vec.end());
		int rem = 0, pr = 0;
		int p = 0, val = get_mx(l, r, vec[0]);
		for (int j = 0; j < s.size(); ++j) {
			auto [x, i] = s[j];
			if (i < r) {
				rem++;
				continue;
			}
			s[pr++] = s[j];
			while (p < vec.size() && vec[p] < x) {
				++p;
				val = p == vec.size()?
				      get_mx(l, r, vec.back()+1):
				      get_mx(l, r, vec[p]);
			}
			if (ql[i] <= l)
				dp[i] = max(dp[i], val);
			else if (ql[i] < r)
				dp[i] = max(dp[i], get_mx(ql[i], r, x));
		}
		s.resize(s.size() - rem);
	}
	int ans = 0;
	Loop (i,0,n)
		ans = max(ans, dp[i]);
	cout << ans << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:104:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for (int j = 0; j < s.size(); ++j) {
      |                   ~~^~~~~~~~~~
Main.cpp:111:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |    while (p < vec.size() && vec[p] < x) {
      |           ~~^~~~~~~~~~~~
Main.cpp:113:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     val = p == vec.size()?
      |           ~~^~~~~~~~~~~~~

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