#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pi;
#define MX 2000010
#define fi first
#define se second
pair<pair<pi, pi>, pi> st[MX];//((nullify left, nullify right), range)
ll pos[MX] = {0};
#define INF 1000000007
ll querylf(ll l, ll r){
--l; --r;
//querying the st
ll cseg = pos[l], nul = 0, rm = 0;
bool wincon = true;
vector<ll> idx;
while(wincon){
wincon = (st[cseg].se.se != r);
if(cseg%2==0){
if(st[cseg].se.se < r){
cseg/=2;
}
else if(st[cseg].se.se == r){
idx.push_back(cseg);
}
else{
if(st[2*cseg].se.se < r){
idx.push_back(2*cseg);
cseg*=2;
cseg++;
}
else{
cseg*=2;
}
}
}
else{
if(st[cseg].se.se < r){
idx.push_back(cseg);
cseg-=1;
cseg/=2;
cseg++;
}
else if(st[cseg].se.se == r){
idx.push_back(cseg);
}
else{
if(st[2*cseg].se.se < r){
idx.push_back(2*cseg);
cseg*=2;
cseg++;
}
else{
cseg*=2;
}
}
}
}
//now process all in idx
for(ll two = 0; two < idx.size(); two++){
ll tp = rm - st[idx[two]].fi.fi.fi;
if(tp >= 0){rm+=tp;}
else{
rm = st[idx[two]].fi.fi.se;
nul -= tp;
}
}
return nul;
}
ll queryrt(ll l, ll r){
--l; --r;
//querying the st
ll cseg = pos[l], nul = 0, rm = 0;
bool wincon = true;
vector<ll> idx;
while(wincon){
wincon = (st[cseg].se.se != r);
if(cseg%2==0){
if(st[cseg].se.se < r){
cseg/=2;
}
else if(st[cseg].se.se == r){
idx.push_back(cseg);
}
else{
if(st[2*cseg].se.se < r){
idx.push_back(2*cseg);
cseg*=2;
cseg++;
}
else{
cseg*=2;
}
}
}
else{
if(st[cseg].se.se < r){
idx.push_back(cseg);
cseg-=1;
cseg/=2;
cseg++;
}
else if(st[cseg].se.se == r){
idx.push_back(cseg);
}
else{
if(st[2*cseg].se.se < r){
idx.push_back(2*cseg);
cseg*=2;
cseg++;
}
else{
cseg*=2;
}
}
}
}
//now process all in idx
for(ll two = idx.size()-1; two > -1; --two){
ll tp = rm - st[idx[two]].fi.se.fi;
if(tp >= 0){rm+=tp;}
else{
rm = st[idx[two]].fi.se.se;
nul -= tp;
}
}
return nul;
}
int main(){
ll n;
cin >> n;
string vote;
cin >> vote;
//initialise segtree?
pi pinf = make_pair(INF, 0);
st[1] = make_pair(make_pair(pinf, pinf), make_pair(0, n-1));
for(ll one = 2; one < MX; one++){
st[one] = make_pair(make_pair(pinf, pinf), make_pair(-1, -1));
}
for(ll one = 1; one < MX; one++){
if(st[one].se.fi != st[one].se.se){
ll md = st[one].se.fi+st[one].se.se;
md/=2;
st[2*one] = make_pair(make_pair(pinf, pinf), make_pair(st[one].se.fi, md));
st[2*one+1] = make_pair(make_pair(pinf, pinf), make_pair(md+1, st[one].se.se));
}
else{
if(pos[st[one].se.fi] == 0){
pos[st[one].se.fi] = one;
}
}
}
//calculate segtree
ll mbk = 0;
for(ll one = 0; one < n; one++){
ll blk = pos[one];
mbk = max(mbk, blk);
if(vote[one] == 'C'){
st[blk].fi.fi.fi = 0;
st[blk].fi.fi.se = 1;
st[blk].fi.se.fi = 0;
st[blk].fi.se.se = 1;
}
else{
st[blk].fi.fi.fi = 1;
st[blk].fi.fi.se = 0;
st[blk].fi.se.fi = 1;
st[blk].fi.se.se = 0;
}
}
for(ll one = mbk; one > 1; one-=2){
if(st[one].fi.fi.fi < INF){
ll tbk = (one-1)/2;
st[tbk].fi.fi.fi = st[one-1].fi.fi.fi;
ll tp = st[one-1].fi.fi.se - st[one].fi.fi.fi;
if(tp >= 0){st[tbk].fi.fi.se = tp + st[one].fi.fi.se;}
else{
st[tbk].fi.fi.se = st[one].fi.fi.se;
st[tbk].fi.fi.fi -= tp;
}
st[tbk].fi.se.fi = st[one].fi.se.fi;
tp = st[one].fi.se.se - st[one-1].fi.se.fi;
if(tp >= 0){st[tbk].fi.se.se = tp+st[one-1].fi.se.se;}
else{
st[tbk].fi.se.se = st[one-1].fi.se.se;
st[tbk].fi.se.fi -= tp;
}
}
}
ll q;
cin >> q;
ll l, r;
for(ll one = 0; one < q; one++){
cin >> l >> r;
cout << max(querylf(l, r), queryrt(l, r)) << endl;
}
}
Compilation message
election.cpp: In function 'll querylf(ll, ll)':
election.cpp:69:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll two = 0; two < idx.size(); two++){
~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
94300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
94300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
94300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
