oj.uz

답안 #463395

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
463395 2021-08-11T05:39:19 Z amunduzbaev Exam (eJOI20_exam) C++14
39 / 100
 927 ms 392592 KB 
#include "bits/stdc++.h"
using namespace std;

#define int long long

void solve1(int n, vector<int>& a, vector<int>& b){
	vector<int> dp(n);
	if(n <= 5005){
		vector<array<int, 3>> tmp;
		for(int i=0;i<n;i++){
			tmp.push_back({a[i], 0, i});
			tmp.push_back({b[i], 1, i});
		}
		
		sort(tmp.begin(), tmp.end());
		for(int last=0, i=0;i<(int)tmp.size();){
			int j = i;
			while(j < (int)tmp.size() && tmp[j][0] == tmp[i][0]) j++;
			while(i < j){
				if(tmp[i][1]){
					b[tmp[i][2]] = last;
				} else {
					a[tmp[i][2]] = last;
				} i++; 
			} last++;
		}
		
		//~ for(int i=0;i<n;i++) cout<<a[i]<<" ";
		//~ cout<<endl;
		//~ for(int i=0;i<n;i++) cout<<b[i]<<" ";
		//~ cout<<endl;
		
		vector<vector<int>> cnt(2 * n, vector<int>(n));
		for(int i=0;i<n;i++){
			assert(b[i] < 2 * n);
			cnt[b[i]][i]++;
			if(i + 1 < n){
				for(int j=0;j<2*n;j++){
					cnt[j][i+1] = cnt[j][i];
				}
			}
		}

		//~ int res = 0;
		//~ for(int i=0;i<n;i++){
			//~ int s = i;
			//~ while(s + 1 < n && a[s + 1] <= a[i]) s++;
			//~ for(int r=s;r>=0;r--){
				//~ if(a[r] > a[i]) break;
				//~ for(int l=r;l>=0;l--){
					//~ if(a[l] > a[i]) break;
					//~ dp[r] = max(dp[r], cnt[a[i]][r] - (l ? cnt[a[i]][l-1] - dp[l-1] : 0));
					//~ res = max(res, dp[r]);
				//~ }
			//~ }
		//~ }
		
		int res = 0;
		for(int i=0;i<n;i++){
			int r = i, l = i;
			while(r + 1 < n && a[r + 1] <= a[i]) r++;
			while(l > 0 && a[l - 1] <= a[l]) l--;
			vector<int> cnt(n);
			for(int j=0;j<n;j++){
				 if(b[j] == a[i]) cnt[j]++;
				 if(j + 1 < n) cnt[j+1] = cnt[j];
			}

			vector<int> pref(n);
			for(int i=0;i<n;i++){
				pref[i] = max(pref[i], dp[i] - cnt[i]);
				if(i + 1 < n) pref[i+1] = pref[i];
			}

			for(int j=l;j<=r;j++){
				dp[j] = max(dp[j], cnt[j] + (j ? pref[j - 1] : 0));
			}
		}
		
		//~ for(int i=0;i<n;i++) cout<<dp[i]<<" ";
		//~ cout<<"\n";
		
		for(int i=0;i<n;i++) res = max(res, dp[i]);
		
		cout<<res<<"\n";
	} else {
		
	}
}

void solve2(int n, vector<int>& a, vector<int>& b){
	int last = 0, cnt = 0, res = 0;
	for(int i=0;i<n;i++){
		if(a[i] > b[0]){
			if(cnt){
				res += (i - last);
			}
			
			cnt = 0, last = i + 1;
		} else {
			cnt |= (a[i] == b[i]);
		}
	} if(cnt){
		res += (n - last);
	}
	
	cout<<res<<"\n";
}

void solve(){
	int n; cin>>n;
	vector<int> a(n), b(n);
	for(auto& x : a) cin>>x;
	for(auto& x : b) cin>>x;
	
	int mx = 0, mn = 1e9;
	for(auto x : b) mx = max(mx, x), mn = min(mn, x);
	if(mx == mn){
		solve2(n, a, b);
		return;
	}
	
	if(n <= 5005){
		solve1(n, a, b);
	} else {
		solve2(n, a, b);
	}
}

/*

3
1 2 3
2 2 2

*/

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t = 1;
	//~ cin>>t;
	while(t--) solve();
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 5 ms 588 KB Output is correct
3 Correct 20 ms 1740 KB Output is correct
4 Correct 15 ms 1868 KB Output is correct
5 Correct 28 ms 1872 KB Output is correct
6 Correct 16 ms 1888 KB Output is correct
7 Correct 19 ms 1868 KB Output is correct
8 Correct 25 ms 1868 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 6 ms 4300 KB Output is correct
3 Correct 138 ms 63224 KB Output is correct
4 Correct 802 ms 361800 KB Output is correct
5 Correct 884 ms 392480 KB Output is correct
6 Correct 927 ms 392484 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 883 ms 392592 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Incorrect 0 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 6 ms 4300 KB Output is correct
9 Correct 138 ms 63224 KB Output is correct
10 Correct 802 ms 361800 KB Output is correct
11 Correct 884 ms 392480 KB Output is correct
12 Correct 927 ms 392484 KB Output is correct
13 Incorrect 0 ms 204 KB Output isn't correct
14 Halted 0 ms 0 KB -