Submission #419886

#	Time	Username	Problem	Language	Result	Execution time	Memory
419886		Berted	Financial Report (JOI21_financial)	C++14	100 / 100	583 ms	11440 KiB

Main

#include <iostream>
#include <algorithm>
#include <set>
#define pii pair<int, int>
#define fst first
#define snd second

using namespace std;

const int SZ = (1 << 20) + 5;

int N, D;
int DP[300001], seg[SZ];
pii A[300001];

set<pii> S;

void upd(int idx, int L, int R, int x, int v)
{
	if (L == R) {seg[idx] = v;}
	else if (L < R)
	{
		int M = L + R >> 1;
		if (x <= M) upd(2 * idx, L, M, x, v);
		else upd(2 * idx + 1, M + 1, R, x, v);
		seg[idx] = max(seg[2 * idx], seg[2 * idx + 1]);
	}
}

int qry(int idx, int L, int R, int l, int r)
{
	l = max(L, l); r = min(R, r);
	if (l <= r)
	{
		if (L == l && R == r) return seg[idx];
		else
		{
			int M = L + R >> 1;
			return max(qry(2 * idx, L, M, l, r), qry(2 * idx + 1, M + 1, R, l, r));
		}
	}
	return 0;
}

void delet(int x)
{
	auto it = S.lower_bound({x + 1, -1});
	if (it != S.begin())
	{
		it = prev(it);
		if (it -> fst <= x && x <= it -> snd)
		{
			pii r = *it; S.erase(it);
			if (x - r.fst >= D) S.insert({r.fst, x - 1});
			if (r.snd - x >= D) S.insert({x + 1, r.snd});
		}
	}
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> N >> D;
	for (int i = 0; i < N; i++)
	{
		cin >> A[i].fst; A[i].snd = -(i + 1);
	}
	sort(A, A + N);

	int res = 0;
	S.insert({1, N});
	for (int i = 0; i < N; i++)
	{
		//cerr << "i: " << i << "\n";
		int id = -A[i].snd;
		delet(id);
		//cerr << "id: " << id << "\n";

		int l; auto it = S.upper_bound({id, -1});
		if (it != S.begin()) {l = prev(it) -> snd + 1;}
		else {l = 1;}

		//cerr << "l: " << l << "\n";
		DP[id] = qry(1, 1, N, l, id) + 1;
		upd(1, 1, N, id, DP[id]);
		res = max(res, DP[id]);
	}

	cout << res << "\n";
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void upd(int, int, int, int, int)':
Main.cpp:23:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   int M = L + R >> 1;
      |           ~~^~~
Main.cpp: In function 'int qry(int, int, int, int, int)':
Main.cpp:38:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |    int M = L + R >> 1;
      |            ~~^~~

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