Submission #1108071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108071		matu	Election (BOI18_election)	C++17	0 / 100	2 ms	592 KiB

election

#include <bits/stdc++.h>
// #include <tr2/dynamic_bitset>
 
using namespace std;
// using namespace tr2;
#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const long double eps = 1e-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randgen(int left, int right) {
    return uniform_int_distribution<int>(left, right)(rng);
}
long long randgenll(long long left, long long right) {
    return uniform_int_distribution<long long>(left, right)(rng);
}
 
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
struct Mint
{
    int val;
    Mint(int x = 0)
    {
        val = x % mod;
    }
    Mint(long long x)
    {
        val = x % mod;
    }
    Mint operator+(Mint oth)
    {
        return val + oth.val;
    }
    Mint operator*(Mint oth)
    {
        return 1LL * val * oth.val;
    }
    Mint operator-(Mint oth)
    {
        return val - oth.val + mod;
    }
    Mint fp(Mint a, long long n){
        Mint p = 1;
        while(n){
            if(n & 1){
                p = p * a;
            }
            a = a * a;
            n /= 2;
        }
        return p;
    }
    Mint operator/(Mint oth){
        Mint invers = fp(oth, mod - 2);
        return 1LL * val * invers.val;
    }
    friend ostream& operator << (ostream& os, const Mint& lol){
        os << lol.val;
        return os;
    }
};
 
struct AINT{
    vector<ll> aint;
    vector<ll> lazy;
  
    AINT(int n){
       
        aint.assign(n * 4 + 1,-1e9);
        //lazy.assign(n * 4 + 1, -1);
    }
    void update(int v, int tl, int tr, int pos, int val){
        if(tl == tr){
            aint[v] = val;
            return;
        }
        int tm = (tl + tr) / 2;
        if(pos <= tm) update(v * 2, tl ,tm, pos, val);
        else update(v * 2 + 1, tm + 1, tr, pos,val);
        aint[v] = max(aint[v * 2], aint[v * 2 + 1]);
    }
    int query(int v, int tl, int tr, int l, int r){
        
        int tm = (tl + tr) / 2;
        if(l <= tl && r >= tr) return aint[v];
        if(l > tr || r < tl) return -1e9;
        return max(query(v * 2, tl, tm,l,r), query(v * 2 + 1, tm + 1, tr, l,r));
        
    }
};
struct AIB{
    vector<int> aib;
    AIB(int n){
        aib.assign(n + 1,0);
    
    }
    void update(int pos, int val){
        for(; pos < aib.size(); pos += (pos & -pos)){
            aib[pos] += val;
        }
    }
    int query(int pos){
        int pl = 0;
   
        for(; pos > 0; pos -= (pos & -pos)) pl += aib[pos];
        return pl;
    }
};
 
int red = 0;
 
int ______________________________________________________________________________________________________________________________________________;
 
void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = '.' + s;
    vector<int> sp1(n + 1), sp2(n + 2);
    AINT aint1(n + 1), aint2(n + 1);
    for(int i = 1; i <= n; i++){
        sp1[i] = sp1[i-1] + (s[i] == 'C' ? -1 : 1);
        aint1.update(1, 1, n, i, sp1[i]);
    }
    for(int i = n; i >= 1; i--){
        sp2[i] = sp2[i + 1] + (s[i] == 'C' ? -1 : 1);
        aint2.update(1,1,n,i,sp2[i]);
    }
    
    int q;
    cin >> q;
    while(q--){
        int  l, r;
        cin >> l >> r;
        int pl = max(aint1.query(1,1,n, l,r) - sp1[l-1], aint2.query(1,1,n,l,r) - sp2[r+ 1]);
        pl = max(pl,0);
        cout << pl << '\n';
    }
}
int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    
    int t = 1; 
    if(red) cin >> t;
   
    while(t--){
        solve();
    }
 
 
}
 
 
/*
 4 1
0 0 1
 
 
j + 1 + p >= d
p >= d - j - 1
 
i + j >= d
 
j >= d - i;
*/

Compilation message (stderr)

election.cpp: In member function 'void AIB::update(int, int)':
election.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(; pos < aib.size(); pos += (pos & -pos)){
      |               ~~~~^~~~~~~~~~~~

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