제출 #1243886

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243886		Tob	Financial Report (JOI21_financial)	C++20	100 / 100	501 ms	20572 KiB

Main

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 3e5 + 7, ofs = (1 << 19);

int n, d;
int a[N], f[N], ia[N];
int t[2*ofs];

void add(int x, int y) {
	x += ofs;
	t[x] = y;
	while (x /= 2) t[x] = max(t[2*x], t[2*x+1]);
}

int get(int x, int l, int r, int lo = 0, int hi = ofs-1) {
	if (l > r || r < lo || hi < l) return 0;
	if (l <= lo && hi <= r) return t[x];
	int mid = (lo+hi)/2;
	return max(get(2*x, l, r, lo, mid), get(2*x+1, l, r, mid+1, hi));
}

int main () {
	FIO;
	cin >> n >> d;
	
	for (int i = 0; i < n; i++) cin >> a[i], ia[i] = i;
	sort(ia, ia+n, [&](int x, int y){return (ll)a[x]*n-x < (ll)a[y]*n-y;});
	
	set <int> s, s2;
	s.insert(-n-1);
	s.insert(n);
	s2.insert(n);
	
	for (int i = 0; i < n; i++) {
		int x = ia[i];
		int str = 0;
		auto p = s.lower_bound(x);
		int y = *p; --p;
		int z = *p;
		if (y-z > d) s2.erase(y);
		s.insert(x);
		if (y-x > d) s2.insert(y);
		if (x-z > d) s2.insert(x);
		auto pp = --s2.upper_bound(x);
		f[x] = max(1, get(1, *pp, x)+1);
		add(x, f[x]);
	}
	
	int mx = 0;
	for (int i = 0; i < n; i++) mx = max(mx, f[i]);
	
	cout << mx;

	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