oj.uz

Submission #571756

# Submission time Handle Problem Language Result Execution time Memory
571756 2022-06-02T16:11:15 Z bojackduy Election (BOI18_election) C++14
100 / 100
 751 ms 69632 KB 
#include<iostream>
#include<queue>
#include<stack>
#include<algorithm>
#include<string.h>
#define int long long
#define size() size() * 1ll 
#define all(x) (x).begin(), (x).end()
#define allr(x, sz) (x) + 1, (x) + 1 + sz
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define MASK(x) (1LL<<(x))
#define BIT(x,i) (((x)>>(i))&1)
#define numbit(x) __builtin_popcountll(x)

using namespace std;

const int N = 1e6 + 1;
const int M = 1e3 + 1;
const long long mod = 1e9 + 7;
const long long oo = 1e18 + 7;

typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;

template<class t>
bool mini(t &x,t y) {
    if (x > y) {
       x = y;
       return 1;
    }
return 0;
}
template<class t>
bool maxi(t &x,t y) {
    if (x < y) {
       x = y;
       return 1;
    }
return 0;
}
void file() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen(task.in, r, stdin);
    //freopen(task.out, w, stdout);
return ;
}

int n, q;
string s;
struct IT {
    struct node {
        int a, s, l, r;
        node(const int &_a = 0, const int &_s = 0, const int &_l = 0, const int &_r = 0): a(_a), s(_s), l(_l), r(_r) {}
    };
    int n;
    vector<node> st;
    IT(const int &_n = 0): n(_n + 1), st(4 * _n + 1, node()) {}
    node merge(node l, node r) {
        return node(max(l.l + r.r, max(l.s + r.a, l.a + r.s)), l.s + r.s, max(l.l, l.s + r.l), max(l.r + r.s, r.r));
    }
    void adj(int id, int l, int r, int i, int val) {
        if (i < l || r < i) return ;
        if (l == r) {
            st[id].s = val;
            maxi(st[id].a, val);
            maxi(st[id].l, val);
            maxi(st[id].r, val);
        return ;
        }
        int mid = l + r >> 1;
        adj(id << 1, l, mid, i, val);
        adj(id << 1 | 1, mid + 1, r, i, val);
        st[id] = merge(st[id << 1], st[id << 1 | 1]);
    }
    node get(int id, int l, int r, int u, int v) {
        if (v < l || r < u) return node();
        if (u <= l && r <= v) return st[id];
        int mid = l + r >> 1;
    return merge(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }
};
void solve(int test = -1) {
    cin >> n >> s >> q;
    IT it(n);
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == 'T') it.adj(1, 1, n, i, 1); else it.adj(1, 1, n, i, -1);
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << it.get(1, 1, n, l, r).a << '\n';
    }
    
}

int32_t main()  {
    file();
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
return 0;
}

Compilation message

election.cpp: In member function 'void IT::adj(long long int, long long int, long long int, long long int, long long int)':
election.cpp:76:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |         int mid = l + r >> 1;
      |                   ~~^~~
election.cpp: In member function 'IT::node IT::get(long long int, long long int, long long int, long long int, long long int)':
election.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 584 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 612 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 584 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 612 KB Output is correct
6 Correct 77 ms 10476 KB Output is correct
7 Correct 78 ms 10328 KB Output is correct
8 Correct 71 ms 10316 KB Output is correct
9 Correct 70 ms 10396 KB Output is correct
10 Correct 74 ms 10272 KB Output is correct
11 Correct 83 ms 10540 KB Output is correct
12 Correct 90 ms 10440 KB Output is correct
13 Correct 88 ms 10528 KB Output is correct
14 Correct 74 ms 10484 KB Output is correct
15 Correct 75 ms 10400 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 584 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 612 KB Output is correct
6 Correct 77 ms 10476 KB Output is correct
7 Correct 78 ms 10328 KB Output is correct
8 Correct 71 ms 10316 KB Output is correct
9 Correct 70 ms 10396 KB Output is correct
10 Correct 74 ms 10272 KB Output is correct
11 Correct 83 ms 10540 KB Output is correct
12 Correct 90 ms 10440 KB Output is correct
13 Correct 88 ms 10528 KB Output is correct
14 Correct 74 ms 10484 KB Output is correct
15 Correct 75 ms 10400 KB Output is correct
16 Correct 693 ms 68532 KB Output is correct
17 Correct 641 ms 68556 KB Output is correct
18 Correct 685 ms 68676 KB Output is correct
19 Correct 589 ms 68176 KB Output is correct
20 Correct 722 ms 67736 KB Output is correct
21 Correct 747 ms 69444 KB Output is correct
22 Correct 751 ms 69328 KB Output is correct
23 Correct 691 ms 69632 KB Output is correct
24 Correct 698 ms 69260 KB Output is correct
25 Correct 720 ms 68892 KB Output is correct