Submission #833939

#	Time	Username	Problem	Language	Result	Execution time	Memory
833939		vjudge1	Exam (eJOI20_exam)	C++17	14 / 100	1082 ms	5328 KiB

exam

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

// os.erase(os.find_by_order(os.order_of_key(val)));
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define MAX LLONG_MAX
#define MOD 1000000007
#define int long long
#define ll __int128
#define endl '\n'
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define pv(x) for (auto i : x) cout << i << ' '; cout << endl;
#define vini(x, y) for (int i = 0; i < y; i++) cin >> x[i];
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a * (b / gcd(a,b)))
#define countonbit(a) __builtin_popcountll(a)

using namespace std;

void solve()
{
	int a; cin >> a;
	int counter = 0;
	vector <int> arr(a), key(a);
	vini(arr, a); vini(key, a);
	vector <pii> arr2(a);
	for (int i = 0; i < a; i++) arr2[i] = {arr[i], i};	
	sort(all(arr2));
	
	bool ok = true;
	for (int i = 0; i < a - 1; i++)
	{
		if (key[i] != key[i + 1]) ok = false;
	}
	if (ok)
	{
		int k = key[0];
		for (int i = 0; i < a; i++)
		{
			if (arr[i] == k)
			{
				for (int j = i - 1; j >= 0; j--)
				{
					if (arr[j] > arr[i]) break;
					arr[j] = arr[i];
				}
				
				for (int j = i + 1; j < a; j++)
				{
					if (arr[j] > arr[i]) break;
					arr[j] = arr[i];
				}
			}
		}
	}
	else
	{
		for (int i = 0; i < a; i++)
		{
			int ind = arr2[i].se;
			int left = ind, right = ind;
			int h = arr2[i].fi;
			
			int lg = 0, rg = 0;
			for (int j = ind - 1; j >= 0; j--)
			{
				if (arr[j] > h) break;
				left = j;
				lg += arr[j] == key[j];
			}
			
			for (int j = ind + 1; j < a; j++)
			{
				if (arr[j] > h) break;
				right = j;
				rg += arr[j] == key[j];
			}
			
			// LEFT
			int mostl = 0, lefttill = ind;
			int g = 0, templ = lg;
			for (int j = ind - 1; j >= left; j--)
			{
				if (arr[j] == key[j]) templ--;
				if (key[j] == h) g++;
				if (g + templ > lg)
				{
					if ((g + templ) - lg > mostl)
					{
						mostl = (g + templ) - lg;
						lefttill = j;
					}
				}
			}
			for (int j = ind; j >= lefttill; j--) arr[j] = h;
	
			// RIGHT
			int mostr = 0, righttill = ind;
			g = 0;
			int tempr = rg;
			for (int j = ind + 1; j <= right; j++)
			{
				if (arr[j] == key[j]) tempr--;
				if (key[j] == h) g++;
				if (g + tempr > rg)
				{
					if ((g + tempr) - rg > mostr)
					{
						mostl = (g + tempr) - lg;
						righttill = j;
					}
				}
			}
			
			for (int j = ind; j <= righttill; j++) arr[j] = h;
		}
	}
	
	for (int i = 0; i < a; i++) counter += arr[i] == key[i];
	
	cout << counter << endl;
}

int32_t main()
{
 	ios::sync_with_stdio(false); cin.tie(NULL);

	int a = 1;
	//cin >> a;
	while(a--) solve();
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 16
• Subtask 6: 0 / 22