Submission #820245

#	Time	Username	Problem	Language	Result	Execution time	Memory
820245		Zanite	Exam (eJOI20_exam)	C++17	100 / 100	512 ms	295360 KiB

exam

#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 / 14
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22