/*
ID: varunra2
LANG: C++
TASK: elections
*/
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif
#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second
const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<ll> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions
struct node{
ll pref = 0;
ll suf = 0;
ll tot = 0;
ll ret = 0;
};
node comb(node a, node b) {
node ret;
ret.pref = max(0ll, max(a.pref, a.tot + b.pref));
ret.suf = max(0ll, max(b.suf, b.tot + a.suf));
ret.tot = a.tot + b.tot;
ret.ret = max(max(a.ret + b.tot, a.tot + b.ret), a.pref + b.suf);
return ret;
}
vector<node> segtree;
VI l;
VI r;
string s;
VI vals;
int n;
int q;
node bad;
void init() {
l.resize(q);
r.resize(q);
segtree.resize(4 * n);
vals.resize(n);
}
void build(int l = 0, int r = n - 1, int node = 0) {
if(l == r) {
segtree[node].pref = max(0ll, vals[l]);
segtree[node].suf = max(0ll, vals[l]);
segtree[node].tot = vals[l];
segtree[node].ret = (vals[l] == 1 ? 1 : 0);
return;
}
int mid = (l + r)/2;
build(l, mid, 2 * node + 1);
build(mid + 1, r, 2 * node + 2);
segtree[node] = comb(segtree[2 * node + 1], segtree[2 * node + 2]);
}
node qry(int tl, int tr, int l, int r, int node) {
if(tl > tr) return bad;
if(tl > r or tr < l) return bad;
if(tl >= l and tr <= r) {
return segtree[node];
}
int mid = (tl + tr)/2;;
return comb(qry(tl, mid, l, r, 2 * node + 1), qry(mid + 1, tr, l, r, 2 * node + 2));
}
int qry(int l, int r) {
node ret = qry(0, n - 1, l, r, 0);
return ret.ret;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("elections.in", "r", stdin);
freopen("elections.out", "w", stdout);
#endif
cin.sync_with_stdio(0); cin.tie(0);
cin >> n;
cin >> s;
cin >> q;
init();
for(int i = 0; i < q; i++) {
cin >> l[i] >> r[i];
l[i]--;
r[i]--;
}
for(int i = 0; i < n; i++) {
vals[i] = (s[i] == 'C' ? -1 : 1);
}
build();
for(int i = 0; i < q; i++) {
cout << qry(l[i], r[i]) << '\n';
}
return 0;
}
Compilation message
election.cpp: In function 'int main()':
election.cpp:122:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
122 | freopen("elections.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:123:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
123 | freopen("elections.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
640 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
640 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
640 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
