| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 61443 |
2018-07-26T03:41:40 Z |
ainta(#1774) |
Election (BOI18_election) |
C++11 |
|
3 ms |
376 KB |
#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 501000
#define SZ 524288
using namespace std;
struct Tree {
int L, R, S;
}IT[SZ + SZ];
int n;
char p[N_];
Tree Merge(Tree a, Tree b) {
return { max(a.L,a.S + b.L), max(b.R,b.S + a.R),a.S + b.S };
}
void Put(int a, int b) {
a += SZ;
IT[a].L = IT[a].R = max(b, 0);
IT[a].S = b;
while (a != 1) {
a >>= 1;
IT[a] = Merge(IT[a * 2], IT[a * 2 + 1]);
}
}
Tree Calc(int nd, int b, int e, int s, int l) {
if (s > l)return { 0,0,0 };
if (b == s&&e == l)return IT[nd];
int m = (b + e) >> 1;
if (s <= m && l > m){
return Merge(Calc(nd * 2, b, m, s, min(m, l)), Calc(nd * 2 + 1, m + 1, e, max(m + 1, s), l));
}
if (s <= m)return Calc(nd * 2, b, m, s, min(m, l));
if (l > m)return Calc(nd * 2 + 1, m + 1, e, max(m + 1, s), l);
}
int main() {
int i;
scanf("%d", &n);
scanf("%s", p + 1);
for (i = 1; i <= n; i++) {
if (p[i] == 'C')Put(i, -1);
else Put(i, 1);
}
int Q;
scanf("%d", &Q);
while (Q--) {
int b, e;
scanf("%d%d", &b, &e);
Tree tt = Calc(1, 0, SZ-1, b, e);
printf("%d\n", max(tt.L, tt.R));
}
}
Compilation message
election.cpp: In function 'Tree Calc(int, int, int, int, int)':
election.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
election.cpp: In function 'int main()':
election.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
election.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", p + 1);
~~~~~^~~~~~~~~~~~~
election.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
election.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &b, &e);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
