oj.uz

Submission #939569

# Submission time Handle Problem Language Result Execution time Memory
939569 2024-03-06T14:19:19 Z Mighilon Election (BOI18_election) C++17
100 / 100
 395 ms 27412 KB 
#include <bits/stdc++.h>
using namespace std;
 
#ifdef DEBUG
#include "../Library/debug.h"
#else
#define dbg(x...)
// #define cin fin
// #define cout fout
// const string FILE_NAME = "elections"; ifstream fin(FILE_NAME + ".in"); ofstream fout(FILE_NAME + ".out");
#endif
 
typedef long long ll;
// typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
// typedef vector<pl> vpl; 
 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) for (int i = 0; i < (a); ++i)
// #define FORd(i, a, b) for (int i = (b) - 1; i >= (a); --i)
// #define F0rd(i, a) for (int i = (a) - 1; i >= 0; --i)
#define trav(a, x) for (auto& a : x)
#define f first 
#define s second
#define pb push_back
// #define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
 
const char nl = '\n';
const int INF = 1e9;
const int MOD = 1e9 + 7;

struct info{
    int l, r, s, a;
};

/* ostream& operator<< (ostream& stream, info x){ */
/*     stream << x.t << " " << x.c << " " << x.t2 << " " << x.c2; */
/*     return stream; */
/* } */

struct SegTree{
    int size;
    vector<info> t;
    SegTree(int _size){
        if(__builtin_popcount(_size) != 1){
            _size = 1 << (32 - __builtin_clz(_size));
        }
        size = _size;
        t.resize(2 * size);
    }
    info merge(info a, info b){
        info tmp = {0, 0, 0, 0};
        tmp.l = max(a.l, a.s + b.l);
        tmp.r = max(a.r + b.s, b.r);
        tmp.s = a.s + b.s;
        tmp.a = max({a.a + b.s, b.a + a.s, a.l + b.r});
        return tmp;
    }
    info query(int x, int l, int r, int ql, int qr){
        if(l > qr || r < ql){
            return {0, 0, 0, 0};
        }
        if(l >= ql && r <= qr){
            return t[x];
        }
        int m = (l + r) / 2;
        return merge(query(2 * x, l, m, ql, qr), query(2 * x + 1, m + 1, r, ql, qr));
    }
    info query(int l, int r){
        return query(1, 0, size - 1, l, r);
    }

};
 
void solve(){
    int n;
    cin >> n;
    SegTree tree(n);
    for(int i = 0; i < n; ++i){
        char c;
        cin >> c;
        if(c == 'C'){
            tree.t[tree.size + i] = {0, 0, -1, 0};
        }
        else{
            tree.t[tree.size + i] = {1, 1, 1, 1};
        }
    }
    for(int i = tree.size - 1; i > 0; --i){
        tree.t[i] = tree.merge(tree.t[2 * i], tree.t[2 * i + 1]);
    }
    /* for(int i = 1; i < 2 * tree.size; ++i){ */
    /*     cout << i << " " << tree.t[i] << nl; */

    /* } */
    int q; cin >> q;
    for(int i = 0; i < q; ++i){
        int l, r;
        cin >> l >> r; --l, --r;
        info tmp = tree.query(l, r);
        cout << tmp.a << nl;
    }
}
 
int32_t main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int TC = 1;
    // cin >> TC;
    while(TC--){
        solve();
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 39 ms 5568 KB Output is correct
7 Correct 37 ms 5556 KB Output is correct
8 Correct 36 ms 5460 KB Output is correct
9 Correct 34 ms 5460 KB Output is correct
10 Correct 38 ms 5508 KB Output is correct
11 Correct 38 ms 5840 KB Output is correct
12 Correct 38 ms 5716 KB Output is correct
13 Correct 38 ms 5716 KB Output is correct
14 Correct 38 ms 5988 KB Output is correct
15 Correct 45 ms 5628 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 39 ms 5568 KB Output is correct
7 Correct 37 ms 5556 KB Output is correct
8 Correct 36 ms 5460 KB Output is correct
9 Correct 34 ms 5460 KB Output is correct
10 Correct 38 ms 5508 KB Output is correct
11 Correct 38 ms 5840 KB Output is correct
12 Correct 38 ms 5716 KB Output is correct
13 Correct 38 ms 5716 KB Output is correct
14 Correct 38 ms 5988 KB Output is correct
15 Correct 45 ms 5628 KB Output is correct
16 Correct 395 ms 26372 KB Output is correct
17 Correct 287 ms 26104 KB Output is correct
18 Correct 308 ms 26192 KB Output is correct
19 Correct 330 ms 25848 KB Output is correct
20 Correct 318 ms 25424 KB Output is correct
21 Correct 357 ms 27364 KB Output is correct
22 Correct 342 ms 27220 KB Output is correct
23 Correct 357 ms 27412 KB Output is correct
24 Correct 336 ms 27220 KB Output is correct
25 Correct 378 ms 26444 KB Output is correct