Submission #529625

#	Time	Username	Problem	Language	Result	Execution time	Memory
529625		MilosMilutinovic	Financial Report (JOI21_financial)	C++14	100 / 100	587 ms	29804 KiB

Main

#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

int n, d, a[300005], rt[300005], sl[300005], sr[300005], dp[300005];
PII ord[300005];

struct segt
{
	int dat[1200005];
	void modify(int id, int v, int cv = 1, int cl = 1, int cr = n)
	{
		if(cl == cr) {
			dat[cv] = v; return;
		}
		int mid = (cl + cr) >> 1;
		if(id <= mid) modify(id, v, cv << 1, cl, mid);
		else modify(id, v, cv << 1 | 1, mid + 1, cr);
		dat[cv] = max(dat[cv << 1], dat[cv << 1 | 1]);
	}
	int query(int l, int r, int cv = 1, int cl = 1, int cr = n)
	{
		if(cl > cr || cl > r || cr < l) return 0;
		if(l <= cl && cr <= r) return dat[cv];
		int mid = (cl + cr) >> 1;
		return max(query(l, r, cv << 1, cl, mid), query(l, r, cv << 1 | 1, mid + 1, cr));
	}
} tre;

int root(int x)
{
	return rt[x] == x ? x : rt[x] = root(rt[x]);
}
void unite(int x, int y)
{
	x = root(x);
	y = root(y);
	if(x == y) return;
	sl[x] = min(sl[x], sl[y]);
	sr[x] = max(sr[x], sr[y]);
	rt[y] = x;
}

int main()
{
	scanf("%d%d", &n, &d);
	rep1(i, n) scanf("%d", &a[i]);
	rep1(i, n) {
		rt[i] = i;
		sl[i] = max(1, i - d);
		sr[i] = min(n, i + d);
	}
	rep1(i, n) ord[i] = MP(a[i], ~i);
	sort(ord + 1, ord + n + 1);
	set<int> ids;
	rep1(i, n) {
		int id = ~ord[i].second;
		{
			set<int>::iterator it = ids.lower_bound(id);
			if(it != ids.end() && *it <= id + d) unite(id, *it);
		}
		{
			set<int>::iterator it = ids.lower_bound(id);
			if(it != ids.begin() && id - d <= *prev(it)) unite(id, *prev(it));
		}
		ids.insert(id);
		dp[id] = tre.query(sl[root(id)], id) + 1;
		tre.modify(id, dp[id]);
	}
	printf("%d\n", tre.query(1, n));
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  scanf("%d%d", &n, &d);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  rep1(i, n) scanf("%d", &a[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