oj.uz

Submission #833486

# Submission time Handle Problem Language Result Execution time Memory
833486 2023-08-22T06:08:28 Z vjudge1 Exam (eJOI20_exam) C++17
39 / 100
 31 ms 1616 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>

const int INF = 2147483645;
const int maxN = (int)1e5+5;
const ll LLINF = LLONG_MAX;
//const ll mod = 998244353;
const ll mod = 1000000007;

ll dp[maxN];
vector<int> v3;

ll lis (ll n) {
	ll mx = 0;
	for (int i=0; i<n; i++) {
		for (int j=0; j<i; j++) {
			if (v3[i] >= v3[j]) { 
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}
	for (int i=0;i<n;i++) {
		mx = max(mx, dp[i]);
	}
	return mx+1;
}

void st1(vector<int> h, vector<int> t) {
	int n = h.size(), tempans=0;
	vector<pii> v;
	for (int i=0;i<n;i++) {
		v.pb(mp(h[i], i));
		if (h[i] == t[i]) tempans++;
	}
	sort(v.begin(), v.end());
	for (int i=0;i<n;i++) {
		int idx = v[i].second;
		int l[maxN]={}, r[maxN]={};
		int ctr=0, img=0, tmp=idx-1;
		while (tmp >= 0 && h[tmp] <= h[idx]) {
			if (h[idx] == t[tmp]) img++;
			if (h[tmp] == t[tmp]) ctr++;
			l[tmp] = img-ctr;
			tmp--;
		}
//		cout<<ctr<<" "<<img<<'\n';
		int leftest = tmp+1;
		tmp = idx+1; ctr = 0; img = 0;
		while (tmp < n && h[tmp] <= h[idx]) {
			if (h[idx] == t[tmp]) img++;
			if (h[tmp] == t[tmp]) ctr++;
			r[tmp] = img-ctr;
			tmp++;
		}
//		cout<<ctr<<" "<<img<<'\n';
		int rightest = tmp;
		int mxl = 0, mxr = 0, lidx=idx, ridx=idx;
		for (int j=idx-1;j>=leftest;j--) {
			if (mxl < l[j]) {
				mxl = l[j];
				lidx = j;
			}
		}
		for (int j=idx+1;j<rightest;j++) {
			if (mxr < r[j]) {
				mxr = r[j];
				ridx = j;
			}
		}
//		cout<<h[idx]<<" "<<lidx<<" "<<ridx<<" "<<'\n';
		for (int j=lidx;j<=ridx;j++) {
			h[j] = h[idx];
		}
		ctr = 0;
		for (int j=0;j<n;j++) {
			if (h[j] == t[j]) ctr++;
		}
		tempans = max(tempans, ctr);
	}
	int ans = 0;
	for (int i=0;i<n;i++) {
		if (h[i] == t[i]) ans++;
	}
	ans = max(ans, tempans);
	cout<<ans<<'\n';
}

void st3(vector<int> h, vector<int> t) {
	map<int, int> idx;
	int n = h.size();
	for (int i=0;i<n;i++) idx[h[i]] = i;
	for (int i=0;i<n;i++) {
		if (idx.count(t[i]) && i <= idx[t[i]]) v3.pb(t[i]);
	}
	cout<<lis(v3.size())<<'\n';
}

void solv() {
	int n, a, ans=0;
	vector<int> h, t;
	bool inc = true, same = true;
	cin>>n;
	for (int i=0;i<n;i++) {
		cin>>a, h.pb(a);
		if (i > 0) {
			if (a <= h[i-1]) inc = false;
		}
	}
	for (int i=0;i<n;i++) {
		cin>>a, t.pb(a);
		if (a != t[0]) same = false;
	}
	if (inc) {
		st3(h, t);
		return;
	}
	if (!same && n <= 5000) {
		st1(h, t);
		return;
	}
	for (int i=0;i<n;i++) {
		if (h[i] != a) continue;
		int tmp = i-1;
		while (tmp >= 0 && h[tmp] <= a) {
			ans++, tmp--;
		}
		while (i < n && h[i] <= a) {
			ans++, i++;
		}
	}
	cout<<ans<<'\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t=1;
//	cin>>t;
	while (t--) solv();
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 11 ms 1364 KB Output is correct
4 Correct 10 ms 1492 KB Output is correct
5 Correct 17 ms 1492 KB Output is correct
6 Correct 9 ms 1492 KB Output is correct
7 Correct 10 ms 1492 KB Output is correct
8 Correct 20 ms 1616 KB Output is correct

Subtask #3
13.0 / 13.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Incorrect 1 ms 1108 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 31 ms 596 KB Output is correct
11 Correct 10 ms 596 KB Output is correct
12 Correct 10 ms 596 KB Output is correct
13 Correct 1 ms 1108 KB Output is correct
14 Incorrect 1 ms 1108 KB Output isn't correct
15 Halted 0 ms 0 KB -