Submission #737607

#	Time	Username	Problem	Language	Result	Execution time	Memory
737607		Trent	Election (BOI18_election)	C++17	28 / 100	66 ms	29260 KiB

election

#include "bits/stdc++.h"
 
using namespace std;
#define forR(i, a) for(int i = 0; (i) < (a); ++(i))
#define REP(i, a, b) for(int i = (a); (i) < (b); ++i)
#define all(a) a.begin(), a.end()
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define printArr(arr) for(int asdfg : arr) cout << asdfg << ' '; cout << '\n'
#define open(x) freopen(((string) x + ".in").c_str(), "r", stdin); freopen(((string) x + ".out").c_str(), "w", stdout);
typedef long long ll;
typedef long double ld;
struct pii{ll a, b;};
struct tii{ll a, b, c;};
bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}

const int MN = 5e5 + 10, ME = 4 * MN, INF = 1e7;

struct node{
    int mi, ma, mad, lz;
} seg[ME];
int n;

node comb(node a, node b){
    assert(a.lz == 0 && b.lz == 0);
    return {min(a.mi, b.mi), max(a.ma, b.ma), max({a.ma, b.ma, a.mad, b.mad, b.ma - a.mi}), 0};
}
void down(int v){
    if(2*v+1 < MN){
        seg[2*v].mi += seg[v].lz;
        seg[2*v].ma += seg[v].lz;
        seg[2*v].lz += seg[v].lz;
        seg[2*v+1].mi += seg[v].lz;
        seg[2*v+1].ma += seg[v].lz;
        seg[2*v+1].lz += seg[v].lz;
        seg[v].lz = 0;
    }
}
void upd(int l, int r, int by, int v=1, int nl=1, int nr=n){
    down(v);
    if(l > r) return;
    else if(nl == l && nr == r){
        seg[v].mi += by;
        seg[v].ma += by;
        seg[v].lz += by;
        down(v);
    } else {
        int mid = (nl+nr) / 2;
        upd(l, min(mid, r), by, 2*v, nl, mid);
        upd(max(mid+1, l), r, by, 2*v+1, mid+1, nr);
        seg[v] = comb(seg[2*v], seg[2*v+1]);
    }
}
node qry(int l, int r, int v=1, int nl=1, int nr=n){
    down(v);
    if(l > r) return {INF, -INF, 0, 0};
    else if(nl == l && nr == r) return seg[v];
    else {
        int mid = (nl+nr)/2;
        return comb(
            qry(l, min(mid, r), 2*v, nl, mid),
            qry(max(mid+1, l), r, 2*v+1, mid+1, nr)
        );
    }
}

int ans[MN]; vector<pii> qu[MN];
signed main(){
    cin >> n;
    string s; cin >> s;
    int q; cin >> q;
    forR(i, q){
        int l, r; cin >> l >> r;
        qu[l].push_back({r, i});
    }
    for(int l = n; l >= 1; --l){
        int ch = s[l-1] == 'C' ? 1 : -1;
        upd(l, n, ch);
        for(auto [r, i] : qu[l]){
            auto [mi, ma, mad, lz] = comb({0, 0, 0, 0}, qry(l, r));
            int ct = -mi;
            int la = mad;
            int las = qry(r, r).mi - mi;
            ans[i] = ct + la - las;
        }
    }
    forR(i, q) cout << ans[i] << '\n';
}

Compilation message (stderr)

election.cpp: In function 'bool operator<(pii, pii)':
election.cpp:14:63: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   14 | bool operator <(pii a, pii b){ return a.a < b.a || a.a == b.a && a.b < b.b;}
      |                                                    ~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 28 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18