oj.uz

Submission #833939

# Submission time Handle Problem Language Result Execution time Memory
833939 2023-08-22T09:38:52 Z vjudge1 Exam (eJOI20_exam) C++17
14 / 100
 1000 ms 5328 KB 
#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.0 / 14.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 237 ms 976 KB Output is correct
3 Execution timed out 1061 ms 4180 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 12 ms 2260 KB Output is correct
3 Correct 26 ms 4564 KB Output is correct
4 Correct 34 ms 5324 KB Output is correct
5 Execution timed out 1082 ms 5328 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 0 ms 212 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 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -