Submission #535880

#	Time	Username	Problem	Language	Result	Execution time	Memory
535880		pooyashams	Financial Report (JOI21_financial)	C++14	100 / 100	1727 ms	27704 KiB

Main

#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 3e5+10;

int n, D;

#define lc (v<<1)
#define rc (lc|1)

struct node
{
	int l, m, p, s;
	node()
	{
		l = m = p = s = 0;
	}
	node(int _l, int _m, int _p, int _s)
	{
		l = _l;
		m = _m;
		p = _p;
		s = _s;
	}
	inline void upd(const node a, const node b)
	{
		l = a.l+b.l;
		p = a.p;
		if(a.p == a.l)
			p += b.p;
		s = b.s;
		if(b.s == b.l)
			s += a.s;
		m = max(a.s+b.p, max(a.m, b.m));
	}
} seg[maxn*4], res;
void build(int l, int r, int v)
{
	if(r-l == 1)
		return (void)(seg[v] = node(1, 0, 0, 0));
	int m = (l+r) / 2;
	build(l, m, lc);
	build(m, r, rc);
	seg[v].upd(seg[lc], seg[rc]);
}
void ass(int l, int r, int p, int v)
{
	if(r-l == 1)
		return (void)(seg[v] = node(1, 1, 1, 1));
	int m = (l+r) / 2;
	if(p < m)
		ass(l, m, p, lc);
	else
		ass(m, r, p, rc);
	seg[v].upd(seg[lc], seg[rc]);
}
inline void ass(int p)
{
	return ass(0, n, p, 1);
}
void _get(int l, int r, int s, int e, int v)
{
	if(e <= l or r <= s) return;
	if(s <= l and r <= e) return res.upd(res, seg[v]);
	int m = (l+r) / 2;
	_get(l, m, s, e, lc);
	_get(m, r, s, e, rc);
}
inline node get(int s, int e)
{
	res = node();
	_get(0, n, s, e, 1);
	return res;
}

int arr[maxn];
int perm[maxn];
int strt[maxn];

struct mxsgt
{
	vector<int> vals;
	mxsgt()
	{
		vals = vector<int>(n*4, 0);
	}
	void ass(int l, int r, int p, int x, int v)
	{
		if(r-l == 1)
			return (void)(vals[v] = x);
		int m = (l+r)/2;
		if(p < m)
			ass(l, m, p, x, lc);
		else
			ass(m, r, p, x, rc);
		vals[v] = max(vals[lc], vals[rc]);
	}
	int get(int l, int r, int s, int e, int v)
	{
		if(e <= l or r <= s) return 0;
		if(s <= l and r <= e) return vals[v];
		int m = (l+r) / 2;
		return max(get(l, m, s, e, lc), get(m, r, s, e, rc));
	}
	inline void ass(int p, int x)
	{
		ass(0, n, p, x, 1);
	}
	inline int get(int s, int e)
	{
		return get(0, n, s, e, 1);
	}
};

inline int bisect(int l, int r)
{
	if(get(l, r).m < D) return l;
	int i = r;
	while(r-l > 1)
	{
		int m = (l+r) / 2;
		if(get(m, i).m >= D)
			l = m;
		else
			r = m;
	}
	return l;
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> D;
	build(0, n, 1);
	for(int i = 0; i < n; i++)
		cin >> arr[i];
	iota(perm, perm+n, 0);
	sort(perm, perm+n, [&](int i, int j){return arr[i] < arr[j] or (arr[i] == arr[j] and i > j);});
	//for(int i = 0; i < n; i++) cerr << perm[i] << " "; cerr << endl;
	for(int idx = n-1; idx >= 0; idx--)
	{
		int i = perm[idx];
		ass(i);
		strt[i] = bisect(0, i);
		//cerr << i << ": " << strt[i] << endl;
	}
	mxsgt dp;
	int ans = 0;
	for(int idx = 0; idx < n; idx++)
	{
		int i = perm[idx];
		int x = 1+dp.get(strt[i], i);
		dp.ass(i, x);
		ans = max(ans, x);
	}
	cout << ans << endl;
	return 0;
}

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