Submission #651169

#	Time	Username	Problem	Language	Result	Execution time	Memory
651169		ymm	Financial Report (JOI21_financial)	C++17	100 / 100	2169 ms	35564 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 = 1024*3;
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;

__attribute__((optimize("O3,unroll-loops"),target("avx2")))
int get_mx(int l, int r, int x)
{
	int ans = 0;
	if (r-l < 32) {
		Loop (i,l,r)
			ans = ans < dp[i] && a[i] < x? dp[i]: ans;
		return ans;
	}
	while (l&7) {
		ans = ans < dp[l] && a[l] < x? dp[l]: ans;
		++l;
	}
	while (r&7) {
		--r;
		ans = ans < dp[r] && a[r] < x? dp[r]: ans;
	}
	typedef int ymm __attribute__((vector_size(32),aligned(32)));
	ymm vans = {};
	Loop (i,l/8,r/8) {
		ymm vdp = ((ymm *)dp)[i];
		ymm va = ((ymm *)a)[i];
		ymm tmp = va < x;
		ymm mx = vans < vdp? vdp: vans;
		vans = tmp? mx: vans;
	}
	Loop (i,0,8)
		ans = max(ans, vans[i]);
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int d;
	cin >> n >> d;
	vector<pii> srt;
	set<pii> s;
	Loop (i,0,n) {
		cin >> a[i];
		srt.push_back({a[i], i});
		s.insert({a[i], i});
	}
	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]);
			s.erase({a[i], i});
		}
		sort(vec.begin(), vec.end());
		int p = 0, val = get_mx(l, r, vec[0]);
		for (auto [x, i] : s) {
			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));
		}
	}
	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:127:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |    while (p < vec.size() && vec[p] < x) {
      |           ~~^~~~~~~~~~~~
Main.cpp:129:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     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