oj.uz

Submission #820242

# Submission time Handle Problem Language Result Execution time Memory
820242 2023-08-11T02:03:27 Z Zanite Exam (eJOI20_exam) C++17
77 / 100
 439 ms 295420 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 (sub6Limit) {
		Subtask6::solve();
	} else {
		Subtask4::solve();
	}
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 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 21 ms 2004 KB Output is correct
4 Correct 11 ms 2004 KB Output is correct
5 Correct 40 ms 2116 KB Output is correct
6 Correct 13 ms 2004 KB Output is correct
7 Correct 17 ms 2016 KB Output is correct
8 Correct 35 ms 1944 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 71408 KB Output is correct
4 Correct 388 ms 283460 KB Output is correct
5 Correct 396 ms 295280 KB Output is correct
6 Correct 402 ms 295256 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 295420 KB Output is correct
2 Runtime error 127 ms 84556 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 468 KB Output is correct
7 Correct 1 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 1 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 1 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 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 71408 KB Output is correct
10 Correct 388 ms 283460 KB Output is correct
11 Correct 396 ms 295280 KB Output is correct
12 Correct 402 ms 295256 KB Output is correct
13 Correct 1 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 1 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 1 ms 3156 KB Output is correct
20 Correct 2 ms 3156 KB Output is correct
21 Correct 1 ms 3156 KB Output is correct
22 Correct 15 ms 24148 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 439 ms 295308 KB Output is correct
25 Correct 400 ms 295320 KB Output is correct
26 Correct 437 ms 295400 KB Output is correct
27 Correct 414 ms 295272 KB Output is correct
28 Correct 419 ms 295268 KB Output is correct
29 Correct 437 ms 295244 KB Output is correct
30 Correct 422 ms 295268 KB Output is correct
31 Correct 408 ms 295248 KB Output is correct
32 Correct 418 ms 295344 KB Output is correct