| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 74578 |
2018-09-04T11:08:55 Z |
Good |
Election (BOI18_election) |
C++11 |
|
16 ms |
504 KB |
#include <bits/stdc++.h>
#define ff first
#define ss second
#define Maxn 100009
#define ll long long
#define pb push_back
#define Inf 1000000009
#define ppb() pop_back()
#define pii pair <int , int>
#define mid(x, y) (x + y) / 2
#define all(x) x.begin(),x.end()
#define llInf 1000000000000000009
using namespace std;
int n, q, S;
char a[Maxn];
int prt[Maxn];
int ans[Maxn];
int A[Maxn][2];
int T[Maxn * 4][2];
vector <int> v;
vector <pair <pii, int> > Q;
void upd (int x, int l, int r, int v, bool type, int add) {
if (l == r) {
T[v][type] += add;
return;
}
if (x <= mid (l, r))
upd (x, l, mid (l, r), v * 2, type, add);
else
upd (x, mid (l, r) + 1, r, v * 2 + 1, type, add);
T[v][type] = T[v * 2][type] + T[v * 2 + 1][type];
}
int get (int x, int y, int l, int r, int v, bool type) {
if (l > y or r < x)
return 0;
if (l >= x and r <= y)
return T[v][type];
return get (x, y, l, mid (l, r), v * 2, type) + get (x, y, mid (l, r) + 1, r, v * 2 + 1, type);
}
bool cmp (pair <pii, int> x, pair <pii, int> y) {
if (x.ff.ff / S == y.ff.ff / S)
return (x.ff.ss > y.ff.ss);
return (x.ff.ff / S < y.ff.ff / S);
}
int main () {
//freopen ("file.in", "r", stdin);
//freopen ("file.out", "w", stdout);
//srand ((unsigned) time ( NULL ));
//int randomNumber = rand() % 10 + 1;
scanf ("%d %s", &n, a);
S = sqrt (n);
for (int i = 1; i <= n; i++) {
prt[i] = prt[i - 1];
if (a[i - 1] == 'C')
v.pb (i);
else {
prt[i] ++;
if (v.size())
A[i][0] = v.back(), v.ppb();
}
}
v.clear();
for (int i = n; i >= 1; i--) {
if (a[i - 1] == 'C')
v.pb (i);
else
if (v.size())
A[i][1] = v.back(), v.ppb ();
}
scanf ("%d", &q);
for (int i = 1; i <= q; i++) {
int l, r;
scanf ("%d%d", &l, &r);
Q.pb ({{l, r}, i});
}
sort (all (Q), cmp);
int l = 1, r = 1;
for (auto i: Q) {
while (l > i.ff.ff) {
if (A[l - 1][0])
upd (A[l - 1][0], 1, n, 1, 0, 1);
if (A[l - 1][1])
upd (A[l - 1][1], 1, n, 1, 1, 1);
l --;
}
while (l < i.ff.ff) {
if (A[l][0])
upd (A[l][0], 1, n, 1, 0, -1);
if (A[l][1])
upd (A[l][1], 1, n, 1, 1, -1);
l ++;
}
while (r <= i.ff.ss) {
if (A[r][0])
upd (A[r][0], 1, n, 1, 0, 1);
if (A[r][1])
upd (A[r][1], 1, n, 1, 1, 1);
r ++;
}
while (r > i.ff.ss + 1) {
if (A[r - 1][0])
upd (A[r - 1][0], 1, n, 1, 0, -1);
if (A[r - 1][1])
upd (A[r - 1][1], 1, n, 1, 1, -1);
r--;
}
ans[i.ss] = prt[i.ff.ss] - prt[i.ff.ff - 1] - min (get (i.ff.ff, i.ff.ss, 1, n, 1, 0), get (i.ff.ff, i.ff.ss, 1, n, 1, 1));
}
for (int i = 1; i <= q; i++)
printf ("%d\n", ans[i]);
return 0;
}
Compilation message
election.cpp: In function 'int main()':
election.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %s", &n, a);
~~~~~~^~~~~~~~~~~~~~~~
election.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &q);
~~~~~~^~~~~~~~~~
election.cpp:96:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &l, &r);
~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
