Submission #1250708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250708		TIN	Financial Report (JOI21_financial)	C++20	100 / 100	244 ms	8668 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define FNAME "test"

const int N = 3e5 + 5;

int n, D;
int a[N];
int pos[N];
int rnk[N];
int ST[4 * N];

void Task() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cout << fixed << setprecision(9);
	if (fopen(FNAME".inp","r")) {
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

void update(int id, int l, int r, int pos, int val) {
	if (pos < l || r < pos) return;
	if (l == r) {
		ST[id] = val;
		return;
	}
	int m = (l + r) / 2;
	if (pos <= m) update(id * 2, l, m, pos, val);
	else update(id * 2 + 1, m + 1, r, pos, val);
	ST[id] = max(ST[id * 2], ST[id * 2 + 1]);
}

int query(int id, int l, int r, int u, int v) {
	if (u > v) return 0;
	if (v < l || r < u) return 0;
	if (u <= l && r <= v) return ST[id];
	int m = (l + r) / 2;
	int ret = INT_MIN;
	if (u <= m) ret = max(ret, query(id * 2, l, m, u, v));
	if (v > m) ret = max(ret, query(id * 2 + 1, m + 1, r, u, v));
	return ret;
}

int find(int id, int l, int r, int u, int v) {
	if (u > v) return 0;
	if (v < l || r < u || !ST[id]) return 0;
	if (l == r) return l;
	int m = (l + r) / 2;
	return find(id * 2, l, m, u, v) ? : find(id * 2 + 1, m + 1, r, u, v);
}

int find(int x) {
	if (pos[x] == x) {
		int res = find(1, 1, n, x - D, x - 1);
		if (res) pos[x] = find(res);
		return pos[x];
	}
	return pos[x] = find(pos[x]);
}

void Solve() {
	//Your Code
	cin >> n >> D;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) pos[i] = i;
	for (int i = 1; i <= n; i++) rnk[i] = n + 1 - i;
	stable_sort(rnk + 1, rnk + n + 1, [](int i, int j) { return a[i] < a[j]; });
	memset(ST, 0, sizeof(ST));
	for (int i = 1; i <= n; i++) update(1, 1, n, rnk[i], query(1, 1, n, find(rnk[i]) - D, rnk[i] - 1) + 1);
	cout << query(1, 1, n, 1, n);
}

int main() {
	Task();
	Solve();
	cerr << "\nTime run: " << 1000*clock()/CLOCKS_PER_SEC << "ms";
	return 37^37;
}

Compilation message (stderr)

Main.cpp: In function 'void Task()':
Main.cpp:20:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:21:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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