oj.uz

Submission #957274

# Submission time Handle Problem Language Result Execution time Memory
957274 2024-04-03T11:12:59 Z Icelast Election (BOI18_election) C++17
82 / 100
 52 ms 23552 KB 
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*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 2 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 480 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 480 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 47 ms 10192 KB Output is correct
7 Correct 47 ms 10092 KB Output is correct
8 Correct 48 ms 10064 KB Output is correct
9 Correct 41 ms 10060 KB Output is correct
10 Correct 46 ms 10064 KB Output is correct
11 Correct 47 ms 10060 KB Output is correct
12 Correct 49 ms 10216 KB Output is correct
13 Correct 48 ms 10304 KB Output is correct
14 Correct 52 ms 10468 KB Output is correct
15 Correct 47 ms 10164 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 480 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 47 ms 10192 KB Output is correct
7 Correct 47 ms 10092 KB Output is correct
8 Correct 48 ms 10064 KB Output is correct
9 Correct 41 ms 10060 KB Output is correct
10 Correct 46 ms 10064 KB Output is correct
11 Correct 47 ms 10060 KB Output is correct
12 Correct 49 ms 10216 KB Output is correct
13 Correct 48 ms 10304 KB Output is correct
14 Correct 52 ms 10468 KB Output is correct
15 Correct 47 ms 10164 KB Output is correct
16 Runtime error 14 ms 23552 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -