oj.uz

Submission #820245

# Submission time Handle Problem Language Result Execution time Memory
820245 2023-08-11T02:06:10 Z Zanite Exam (eJOI20_exam) C++17
100 / 100
 512 ms 295360 KB 
#include <bits/stdc++.h>
using namespace std;

const int iINF	= 1e9;
const int maxN	= 5023;
const int maxNN	= 100'023;

int N, M, A[maxNN], B[maxNN];
vector<int> compress;

namespace Subtask2 {
	void solve() {
		int qb = B[1];
		int ans = 0, run = 0;
		bool hasB = false;
		for (int i = 1; i <= N; i++) {
			if (A[i] > qb) {
				run = 0;
				hasB = false;
				continue;
			}

			run++;
			if (A[i] == qb) {hasB = true;}
			if (hasB) {
				ans += run;
				run = 0;
			}
		}
		cout << ans << '\n';
	}
}

namespace Subtask4 {
	struct Segtree {
		#define m	((l + r) >> 1)
		#define lc	(pos << 1)
		#define rc	(lc | 1)

		int n;
		vector<int> seg;

		Segtree(int n) : n(n) {
			seg.assign((n << 2) + 1, 0);
		}

		void build(int pos, int l, int r) {
			if (l == r) {
				seg[pos] = A[l];
				return;
			}

			build(lc, l, m);
			build(rc, m+1, r);
			seg[pos] = max(seg[lc], seg[rc]);
		}
		void build() {build(1, 1, n);}

		int query(int pos, int l, int r, int ql, int qr) {
			if (ql <= l && r <= qr) return seg[pos];
			if (l > qr || ql > r || l > r || ql > qr) return -iINF;
			return max(query(lc, l, m, ql, qr), query(rc, m+1, r, ql, qr));
		}
		int query(int ql, int qr) {return query(1, 1, n, ql, qr);}
	};

	void solve() {
		int pos[M+1];
		for (int i = 0; i <= M; i++) pos[i] = -1;
		
		for (int i = 1; i <= N; i++) pos[A[i]] = i;

		Segtree S(N);
		S.build();

		vector<int> nwB;
		for (int i = 1; i <= N; i++) {
			if (pos[B[i]] == -1) continue;

			int l = pos[B[i]];
			int r = i;
			if (l > r) swap(l, r);

			if (S.query(l, r) == B[i]) nwB.push_back(pos[B[i]]);
		}
		// for (auto i : nwB) {cout << i << ' ';} cout << '\n';

		// LIS
		vector<int> LIS;
		for (auto i : nwB) {
			int pos = upper_bound(LIS.begin(), LIS.end(), i) - LIS.begin();
			if (pos == (int)LIS.size()) {
				LIS.push_back(i);
			} else {
				LIS[pos] = i;
			}
		}
		cout << LIS.size() << '\n';
	}
}

namespace Subtask6 {
	int dp[maxN][maxN], mx[maxN][maxN], pf[maxN][maxN];

	void solve() {
		for (int l = 1; l <= N; l++) {
			mx[l][l] = A[l];
			for (int r = l+1; r <= N; r++) {
				mx[l][r] = max(mx[l][r-1], A[r]);
				mx[r][l] = mx[l][r];
			}
		}

		for (int i = 1; i <= N; i++) {
			for (int val = 1; val <= N; val++) {
				pf[i][val] = -iINF;
			}
		}

		pf[0][0] = 0;
		for (int i = 1; i <= N; i++) {
			for (int val = 1; val <= N; val++) {
				if (mx[val][i] == A[val]) {
					dp[i][val] = pf[i-1][val] + (B[i] == A[val]);
					// cout << "dp[" << i << "][" << val << "] = " << dp[i][val] << '\n';
				} else {
					dp[i][val] = -iINF;
				}

				pf[i][val] = max(pf[i][val-1], dp[i][val]);
			}
		}

		int ans = pf[N][N];
		cout << ans << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		compress.push_back(A[i]);
	}
	for (int i = 1; i <= N; i++) {
		cin >> B[i];
		compress.push_back(B[i]);
	}

	sort(compress.begin(), compress.end());
	compress.erase(unique(compress.begin(), compress.end()), compress.end());
	M = compress.size();
	for (int i = 1; i <= N; i++) {
		A[i] = lower_bound(compress.begin(), compress.end(), A[i]) - compress.begin() + 1;
		B[i] = lower_bound(compress.begin(), compress.end(), B[i]) - compress.begin() + 1;
	}

	bool allEqualB = true;
	for (int i = 2; i <= N; i++) {
		if (B[i] != B[1]) allEqualB = false;
	}

	const int sub6Limit = 5000;

	// Subtask4::solve();

	if (allEqualB) {
		Subtask2::solve();
	} else if (N <= sub6Limit) {
		Subtask6::solve();
	} else {
		Subtask4::solve();
	}
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 5 ms 852 KB Output is correct
3 Correct 26 ms 2004 KB Output is correct
4 Correct 14 ms 2004 KB Output is correct
5 Correct 48 ms 2016 KB Output is correct
6 Correct 19 ms 2000 KB Output is correct
7 Correct 16 ms 2004 KB Output is correct
8 Correct 35 ms 2004 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 4 ms 9300 KB Output is correct
3 Correct 56 ms 71444 KB Output is correct
4 Correct 407 ms 283532 KB Output is correct
5 Correct 416 ms 295276 KB Output is correct
6 Correct 428 ms 295248 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 28 ms 1884 KB Output is correct
3 Correct 73 ms 5128 KB Output is correct
4 Correct 76 ms 5904 KB Output is correct
5 Correct 82 ms 6640 KB Output is correct
6 Correct 65 ms 5896 KB Output is correct
7 Correct 66 ms 6140 KB Output is correct
8 Correct 68 ms 5092 KB Output is correct
9 Correct 65 ms 5552 KB Output is correct
10 Correct 56 ms 5740 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 2 ms 3156 KB Output is correct
11 Correct 1 ms 3156 KB Output is correct
12 Correct 1 ms 3156 KB Output is correct
13 Correct 2 ms 3156 KB Output is correct
14 Correct 2 ms 3156 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 0 ms 468 KB Output is correct
8 Correct 4 ms 9300 KB Output is correct
9 Correct 56 ms 71444 KB Output is correct
10 Correct 407 ms 283532 KB Output is correct
11 Correct 416 ms 295276 KB Output is correct
12 Correct 428 ms 295248 KB Output is correct
13 Correct 0 ms 468 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 1620 KB Output is correct
16 Correct 2 ms 3156 KB Output is correct
17 Correct 1 ms 3156 KB Output is correct
18 Correct 1 ms 3156 KB Output is correct
19 Correct 2 ms 3156 KB Output is correct
20 Correct 2 ms 3156 KB Output is correct
21 Correct 2 ms 3232 KB Output is correct
22 Correct 18 ms 24172 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 401 ms 295340 KB Output is correct
25 Correct 447 ms 295300 KB Output is correct
26 Correct 476 ms 295360 KB Output is correct
27 Correct 432 ms 295352 KB Output is correct
28 Correct 416 ms 295312 KB Output is correct
29 Correct 410 ms 295268 KB Output is correct
30 Correct 428 ms 295248 KB Output is correct
31 Correct 411 ms 295352 KB Output is correct
32 Correct 512 ms 295304 KB Output is correct