oj.uz

Submission #489204

# Submission time Handle Problem Language Result Execution time Memory
489204 2021-11-21T14:51:27 Z mat_v Election (BOI18_election) C++14
100 / 100
 865 ms 46216 KB 
#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){
        lejzi[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]){
            //cout << kv(i) - kv(c.xx - 1) << "\n";
            //cout << -min(0,query(1,1,n,c.xx,i) - query(1,1,n,c.xx-1,c.xx-1)) << "\n";
            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

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:123:5: note: in expansion of macro 'ff'
  123 |     ff(i,1,q)cout << ans[i] << "\n";
      |     ^~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12108 KB Output is correct
2 Correct 9 ms 12216 KB Output is correct
3 Correct 9 ms 12220 KB Output is correct
4 Correct 8 ms 12236 KB Output is correct
5 Correct 8 ms 12236 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12108 KB Output is correct
2 Correct 9 ms 12216 KB Output is correct
3 Correct 9 ms 12220 KB Output is correct
4 Correct 8 ms 12236 KB Output is correct
5 Correct 8 ms 12236 KB Output is correct
6 Correct 100 ms 17784 KB Output is correct
7 Correct 98 ms 17508 KB Output is correct
8 Correct 133 ms 17472 KB Output is correct
9 Correct 88 ms 17760 KB Output is correct
10 Correct 97 ms 17684 KB Output is correct
11 Correct 96 ms 17864 KB Output is correct
12 Correct 121 ms 17784 KB Output is correct
13 Correct 93 ms 17900 KB Output is correct
14 Correct 95 ms 17652 KB Output is correct
15 Correct 97 ms 17612 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12108 KB Output is correct
2 Correct 9 ms 12216 KB Output is correct
3 Correct 9 ms 12220 KB Output is correct
4 Correct 8 ms 12236 KB Output is correct
5 Correct 8 ms 12236 KB Output is correct
6 Correct 100 ms 17784 KB Output is correct
7 Correct 98 ms 17508 KB Output is correct
8 Correct 133 ms 17472 KB Output is correct
9 Correct 88 ms 17760 KB Output is correct
10 Correct 97 ms 17684 KB Output is correct
11 Correct 96 ms 17864 KB Output is correct
12 Correct 121 ms 17784 KB Output is correct
13 Correct 93 ms 17900 KB Output is correct
14 Correct 95 ms 17652 KB Output is correct
15 Correct 97 ms 17612 KB Output is correct
16 Correct 857 ms 45288 KB Output is correct
17 Correct 836 ms 43000 KB Output is correct
18 Correct 808 ms 43816 KB Output is correct
19 Correct 765 ms 45304 KB Output is correct
20 Correct 865 ms 44436 KB Output is correct
21 Correct 855 ms 46216 KB Output is correct
22 Correct 858 ms 44476 KB Output is correct
23 Correct 833 ms 45184 KB Output is correct
24 Correct 861 ms 44120 KB Output is correct
25 Correct 835 ms 42944 KB Output is correct