oj.uz

Submission #861661

# Submission time Handle Problem Language Result Execution time Memory
861661 2023-10-16T15:49:30 Z iskhakkutbilim Election (BOI18_election) C++17
100 / 100
 442 ms 76488 KB 
#include <bits/stdc++.h>
 
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define ll long long
 
struct Node{
    ll sum, pref, suff, ans;
};
 
int n, arr[(int)5e5 + 10];
 
struct SegmentTree{
    vector<Node> sgt;
    SegmentTree(int n){
        sgt.resize(4 * n);
    }
    Node merge(Node a, Node b){
        return { a.sum + b.sum, max(a.pref, a.sum + b.pref), max(b.suff, a.suff + b.sum), 
		max({0LL, a.pref + b.suff, a.sum + b.ans, a.ans + b.sum}) };
    }
    void build(int k = 1, int l = 0, int r = n - 1){
        if(l == r){
            sgt[k] = { arr[l], max(0, arr[l]), max(0, arr[l]), max(arr[l], 0) };
            return;
        }
        int m = (l + r) / 2;
        build(k * 2, l, m);
        build(k * 2 + 1, m + 1, r);
        sgt[k] = merge(sgt[k * 2], sgt[k * 2 + 1]);
    }
    Node get(int k, int l, int r, int i, int j){
        if (l > j || r < i) return {0, 0, 0, 0};
        if (i <= l && r <= j) return sgt[k];
        int m = (l + r) / 2;
        return merge(get(k * 2, l, m, i, j), get(k * 2 + 1, m + 1, r, i, j));
    }
 
} sgt(5e5);
 
main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) arr[i] = (s[i] == 'C' ? -1 : 1);
    sgt.build();
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << sgt.get(1, 0, n - 1, --x, --y).ans << '\n';
    }
}

Compilation message

election.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main() {
      | ^~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 63064 KB Output is correct
2 Correct 12 ms 63068 KB Output is correct
3 Correct 11 ms 63068 KB Output is correct
4 Correct 10 ms 63068 KB Output is correct
5 Correct 10 ms 63000 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 63064 KB Output is correct
2 Correct 12 ms 63068 KB Output is correct
3 Correct 11 ms 63068 KB Output is correct
4 Correct 10 ms 63068 KB Output is correct
5 Correct 10 ms 63000 KB Output is correct
6 Correct 48 ms 64688 KB Output is correct
7 Correct 46 ms 64648 KB Output is correct
8 Correct 46 ms 64512 KB Output is correct
9 Correct 43 ms 64592 KB Output is correct
10 Correct 56 ms 64684 KB Output is correct
11 Correct 49 ms 64596 KB Output is correct
12 Correct 49 ms 64644 KB Output is correct
13 Correct 52 ms 64736 KB Output is correct
14 Correct 53 ms 64756 KB Output is correct
15 Correct 50 ms 64728 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 63064 KB Output is correct
2 Correct 12 ms 63068 KB Output is correct
3 Correct 11 ms 63068 KB Output is correct
4 Correct 10 ms 63068 KB Output is correct
5 Correct 10 ms 63000 KB Output is correct
6 Correct 48 ms 64688 KB Output is correct
7 Correct 46 ms 64648 KB Output is correct
8 Correct 46 ms 64512 KB Output is correct
9 Correct 43 ms 64592 KB Output is correct
10 Correct 56 ms 64684 KB Output is correct
11 Correct 49 ms 64596 KB Output is correct
12 Correct 49 ms 64644 KB Output is correct
13 Correct 52 ms 64736 KB Output is correct
14 Correct 53 ms 64756 KB Output is correct
15 Correct 50 ms 64728 KB Output is correct
16 Correct 397 ms 75184 KB Output is correct
17 Correct 362 ms 75112 KB Output is correct
18 Correct 405 ms 75088 KB Output is correct
19 Correct 319 ms 74516 KB Output is correct
20 Correct 442 ms 74216 KB Output is correct
21 Correct 433 ms 76128 KB Output is correct
22 Correct 425 ms 76040 KB Output is correct
23 Correct 438 ms 76488 KB Output is correct
24 Correct 406 ms 75724 KB Output is correct
25 Correct 423 ms 75496 KB Output is correct