Submission #489203

#	Time	Username	Problem	Language	Result	Execution time	Memory
489203		mat_v	Election (BOI18_election)	C++14	0 / 100	8 ms	12108 KiB

election

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,int>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());


int n;
string x;
int niz[500005];
int q;
vector<pii> kveri[500005];
int tr = 0;
int sl[500005];

int lejzi[4 * 5000000 + 1];
int seg[4 * 5000000 + 1];


int bit[500005];
void apd(int x, int dlt){
    while(x <= n){
        bit[x] += dlt;
        x += (x&-x);
    }
}
int kv(int x){
    int ans = 0;
    while(x){
        ans += bit[x];
        x -= (x&-x);
    }
    return ans;
}

void propagate(int node, int l, int r){
    if(lejzi[node] == 0)return;
    seg[node] += lejzi[node];
    if(l < r){
        lejzi[node * 2] += lejzi[node];
        lejzi[node * 2 + 1] += lejzi[node];
    }
    lejzi[node] = 0;
}

void update(int node, int l, int r, int levo, int desno, int val){
    propagate(node, l, r);
    if(levo > r || l > desno)return;
    if(l >= levo && r <= desno){
        seg[node] += val;
        propagate(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    update(node * 2, l, mid, levo, desno, val);
    update(node * 2 + 1, mid + 1, r, levo, desno, val);
    seg[node] = min(seg[node * 2], seg[node * 2 + 1]);
}

int query(int node, int l, int r, int levo, int desno){
    if(levo == 0)return 0;
    propagate(node, l, r);
    if(levo > r || l > desno)return 1e9;
    if(l >= levo && r <= desno)return seg[node];
    int mid = (l + r) / 2;
    return min(query(node * 2, l, mid, levo, desno), query(node * 2 + 1 , mid + 1, r, levo, desno));
}


int ans[500005];

int main()
{

    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> x;
    ff(i,1,n){
        if(x[i - 1] == 'C')niz[i] = 1;
        else niz[i] = -1;
    }
    cin >> q;
    ff(i,1,q){
        int l,r;
        cin >> l >> r;
        kveri[r].pb({l,i});
    }
    ff(i,1,n){
        if(niz[i] == -1){
            sl[i] = tr;
            tr = i;
            apd(i,1);
        }
        else{
            update(1,1,n,i,n,1);
            if(tr){
                update(1,1,n,tr,n,-1);
                apd(tr,-1);
                tr = sl[tr];
            }
        }
        for(auto c:kveri[i]){
            ans[c.yy] = -min(0,query(1,1,n,c.xx,i) - query(1,1,n,c.xx-1,c.xx-1)) + kv(i) - kv(c.xx - 1);
        }
    }
    ff(i,1,q)cout << ans[i] << "\n";
    return 0;
}
/*
11
CCCTTTTTTCC
1
1 11



*/

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
election.cpp:93:5: note: in expansion of macro 'ff'
   93 |     ff(i,1,n){
      |     ^~
election.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
election.cpp:98:5: note: in expansion of macro 'ff'
   98 |     ff(i,1,q){
      |     ^~
election.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
election.cpp:103:5: note: in expansion of macro 'ff'
  103 |     ff(i,1,n){
      |     ^~
election.cpp:6:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    6 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
election.cpp:121:5: note: in expansion of macro 'ff'
  121 |     ff(i,1,q)cout << ans[i] << "\n";
      |     ^~

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