oj.uz

Submission #957275

# Submission time Handle Problem Language Result Execution time Memory
957275 2024-04-03T11:13:51 Z Icelast Election (BOI18_election) C++17
100 / 100
 499 ms 44620 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 5*1e5+5, INF = 4e18+9;
ll n, Q;
string s;
void inp(){
    cin >> n;
    cin >> s;
    s = ' ' + s;
    cin >> Q;
}
struct Node{
    ll L, R, S, res;
};
ll N;
Node T[4*maxn];
Node merg(Node a, Node b){
    Node res;
    res.S = a.S+b.S;
    res.L = max(a.L, a.S+b.L);
    res.R = max(b.R, a.R+b.S);
    res.res = max(max(a.S+b.res, a.res+b.S), a.L+b.R);
    return res;
}
void build_segtree(){
    N = 1;
    while(N < n) N*=2;
    for(int i = 1; i <= n; i++){
        if(s[i] == 'C'){
            T[i+N-1] = {0, 0, -1, 0};
        }else{
            T[i+N-1] = {1, 1, 1, 1};
        }
    }
    for(int i = n+1; i <= N; i++){
        T[i+N-1] = {0, 0, 0, 0};
    }
    for(int i = N-1; i >= 1; i--){
        T[i] = merg(T[i*2], T[i*2+1]);
    }
}
Node get(int node, int low, int high, int l, int r){
    if(low > r || l > high) return {0, 0, 0, 0};
    if(low >= l && r >= high) return T[node];
    int mid = (low+high)/2;
    return merg(get(node*2, low, mid, l, r), get(node*2+1, mid+1, high, l, r));
}
void solve(){
    build_segtree();
    int l, r;
    for(int i = 1; i <= Q; i++){
        cin >> l >> r;
        cout << get(1, 1, N, l, r).res << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    inp();
    solve();
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 56 ms 9108 KB Output is correct
7 Correct 47 ms 9300 KB Output is correct
8 Correct 47 ms 9044 KB Output is correct
9 Correct 40 ms 9192 KB Output is correct
10 Correct 50 ms 9044 KB Output is correct
11 Correct 47 ms 9292 KB Output is correct
12 Correct 46 ms 9224 KB Output is correct
13 Correct 47 ms 9296 KB Output is correct
14 Correct 48 ms 9168 KB Output is correct
15 Correct 47 ms 9048 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 56 ms 9108 KB Output is correct
7 Correct 47 ms 9300 KB Output is correct
8 Correct 47 ms 9044 KB Output is correct
9 Correct 40 ms 9192 KB Output is correct
10 Correct 50 ms 9044 KB Output is correct
11 Correct 47 ms 9292 KB Output is correct
12 Correct 46 ms 9224 KB Output is correct
13 Correct 47 ms 9296 KB Output is correct
14 Correct 48 ms 9168 KB Output is correct
15 Correct 47 ms 9048 KB Output is correct
16 Correct 494 ms 42872 KB Output is correct
17 Correct 391 ms 43396 KB Output is correct
18 Correct 452 ms 43384 KB Output is correct
19 Correct 371 ms 43048 KB Output is correct
20 Correct 495 ms 42852 KB Output is correct
21 Correct 456 ms 44536 KB Output is correct
22 Correct 483 ms 44240 KB Output is correct
23 Correct 495 ms 44620 KB Output is correct
24 Correct 491 ms 44120 KB Output is correct
25 Correct 499 ms 43768 KB Output is correct