oj.uz

Submission #1083268

# Submission time Handle Problem Language Result Execution time Memory
1083268 2024-09-02T20:00:38 Z I_am_Polish_Girl Election (BOI18_election) C++14
0 / 100
 2 ms 348 KB 
#pragma target("arch=icelake-server")

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack> 
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <bitset>

using namespace std;

#define int long long

typedef long long ll;
typedef long double ld;

int log_ = 11;
int inf = 4000000007000000007;

long long mod = 1000000007;

int p = 499;

int NADIYA = 39;



signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;

	vector <int> a(n);

	for (int i = 0; i < n; i++)
	{
		char c;
		cin >> c;

		if (c == 'C')
			a[i] = 1;
		else
			a[i] = -1;
	}

	vector <int> pref1(n);

	int p = 0;
	for (int i = 0; i < n; i++)
	{
		p += a[i];
		pref1[i] = p;
	}

	p = 0;

	vector <int> pref2(n);

	for (int i = n - 1; i >= 0; i--)
	{
		p += a[i];
		pref2[i] = p;
	}

	p = 0;


	int q;
	cin >> q;

	for (int j = 0; j < q; j++)
	{
		int l, r;
		cin >> l >> r;
		l--;
		r--;

		int x = 0;
		if (l != 0)
			x = pref1[l - 1];

		int x2 = pref1[r];
		int mn = x;
		int mx = x2;

		int p_mn = l - 1;
		int p_mx = r;

		for (int i = l; i <= r; i++)
		{
			if (mn > pref1[i])
			{
				p_mn = i;
				mn = min(mn, pref1[i]);
			}

			if (mx < pref1[i])
			{
				p_mx = i;
				mx = max(mx, pref1[i]);
			}
		}

		if (p_mn < p_mx)
		{
			swap(x, x2);
		}

		if ((mx - x2) > (x - mn))
		{
			int ans = (mx - x2);

			if (mn + ans < x)
				ans += x - (mn + ans);

			cout << ans << "\n";
		}
		else
		{
			int ans = (x - mn);

			if (mx > x2 + ans)
				ans += mx - (x2+ ans);

			cout << ans << "\n";
		}
		
	}
}

/*5
1 2 1
2 3 1
2 4 1
1 5 4
*/

Compilation message

election.cpp:1: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    1 | #pragma target("arch=icelake-server")
      |

Subtask #1
0 / 28.0

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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