# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1083268 | I_am_Polish_Girl | Election (BOI18_election) | C++14 | 2 ms | 348 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |