# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
106750 |
2019-04-20T09:28:20 Z |
Hideo |
Election (BOI18_election) |
C++14 |
|
31 ms |
31736 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mk make_pair
#define fr first
#define sc second
#define vi vector < int >
#define vl vector < ll >
#define pi pair < int, int >
#define pii pair < int, pi >
#define vii vector < pi >
const int N = 5e5 + 7;
const int INF = 1e9 + 7;
int pr[2][N];
int n, q;
string s;
pi temp;
struct T{
pair < int, int > t[4 * N];
T(){
memset(t, 0, sizeof t);
}
void build (int v, int l, int r, int id){
if (l == r)
t[v] = {pr[id][l], l};
else {
int mid = (l + r) >> 1;
build(v + v, l, mid, id);
build(v + v + 1, mid + 1, r, id);
t[v] = min(t[v + v], t[v + v + 1]);
}
}
pi get (int v, int l, int r, int ql, int qr){
if (ql <= l && r <= qr)
return t[v];
if (r < ql || l > qr)
return {INF, INF};
int mid = (l + r) >> 1;
return min(get(v + v, l, mid, ql, qr), get(v + v + 1, mid + 1, r, ql, qr));
}
};
T tree[2];
main(){
cin >> n >> s;
s = ' ' + s;
for (int i = 1; i <= n; i++){
pr[0][i] = pr[0][i - 1];
if (s[i] == 'C')
pr[0][i]++;
else
pr[0][i]--;
}
tree[0].build(1, 1, n, 0);
for (int i = n; i >= 1; i--){
pr[1][i] = pr[1][i + 1];
if (s[i] == 'C')
pr[1][i]++;
else
pr[1][i]--;
}
tree[1].build(1, 1, n, 1);
cin >> q;
for (int i = 1; i <= q; i++){
int l1, r1, l2, r2;
int v1, v2 = 0, v3;
int y = 0;
scanf("%d%d", &l1, &r2);
temp = tree[0].get(1, 1, n, l1, r2);
temp.fr -= pr[0][l1 - 1];
r1 = temp.sc;
l2 = r1 + 1;
v1 = abs(min(0, temp.fr));
if (l2 <= r2){
temp = tree[1].get(1, 1, n, l2, r2);
temp.fr -= pr[1][r2 + 1];
v2 = abs(min(0, temp.fr));
y = pr[1][l2] - pr[1][r2 + 1] + v2;
}
temp = tree[1].get(1, 1, n, l1, r1);
temp.fr -= pr[1][r1 + 1];
v3 = abs(min(0, temp.fr));
printf("%d\n", v1 + v2 + max(0, v3 - v1 - y));
}
}
Compilation message
election.cpp:51:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
election.cpp: In function 'int main()':
election.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &l1, &r2);
~~~~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
31 ms |
31736 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
31 ms |
31736 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
31 ms |
31736 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |