oj.uz

Submission #480015

# Submission time Handle Problem Language Result Execution time Memory
480015 2021-10-14T09:10:24 Z SlavicG Election (BOI18_election) C++17
100 / 100
 557 ms 22232 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()
 
const int N = 5e5;
struct node{
    int pref;
    int suf;
    int sum;
    int ans;
};

node t[4 * N];
int a[N];

node merge(node a, node b){
    node c;
    c.sum = a.sum + b.sum;
    c.pref = max(a.pref, a.sum + b.pref);
    c.suf = max(b.suf, b.sum + a.suf);
    c.ans = max({0, a.pref + b.suf, a.sum + b.ans, b.sum + a.ans});

    return c;
}
void build(int i, int l, int r)
{
    if(l == r){
        t[i].pref = t[i].suf = max(0, a[l]);
        t[i].sum = a[l];
        t[i].ans = max(0, a[l]);
        return;
    }
    int mid = (l + r) / 2;

    build(2 * i, l, mid);
    build(2 * i + 1, mid + 1, r);
    t[i] = merge(t[2 * i], t[2 * i + 1]);
}
node neutral = {0, 0, 0, 0};
node query(int i, int l, int r, int tl, int tr)
{
    if(l > tr || r < tl)return neutral;
    if(l >= tl && r <= tr)return t[i];

    int mid = (l + r) / 2;

    return merge(query(2 * i, l, mid, tl, tr), query(2 * i + 1, mid + 1, r, tl, tr));
}
void solve()
{  
    int n, q;
    string s;
    cin >> n >> s >> q;

    for(int i = 0;i < n;++i){
        a[i] = (s[i] == 'C' ? -1 : 1);
    }
    build(1, 0, n - 1);

    while(q--)
    {
        int l, r;
        cin >> l >> r;
        cout << query(1, 0, n - 1, l - 1, r - 1).ans << "\n";
    }

}   
 
int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 58 ms 5064 KB Output is correct
7 Correct 59 ms 5064 KB Output is correct
8 Correct 50 ms 5072 KB Output is correct
9 Correct 51 ms 5060 KB Output is correct
10 Correct 54 ms 4940 KB Output is correct
11 Correct 56 ms 5188 KB Output is correct
12 Correct 58 ms 5280 KB Output is correct
13 Correct 57 ms 5112 KB Output is correct
14 Correct 59 ms 5132 KB Output is correct
15 Correct 53 ms 5136 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 58 ms 5064 KB Output is correct
7 Correct 59 ms 5064 KB Output is correct
8 Correct 50 ms 5072 KB Output is correct
9 Correct 51 ms 5060 KB Output is correct
10 Correct 54 ms 4940 KB Output is correct
11 Correct 56 ms 5188 KB Output is correct
12 Correct 58 ms 5280 KB Output is correct
13 Correct 57 ms 5112 KB Output is correct
14 Correct 59 ms 5132 KB Output is correct
15 Correct 53 ms 5136 KB Output is correct
16 Correct 537 ms 21232 KB Output is correct
17 Correct 442 ms 21224 KB Output is correct
18 Correct 477 ms 21204 KB Output is correct
19 Correct 424 ms 20716 KB Output is correct
20 Correct 503 ms 20352 KB Output is correct
21 Correct 512 ms 22104 KB Output is correct
22 Correct 557 ms 21960 KB Output is correct
23 Correct 525 ms 22232 KB Output is correct
24 Correct 554 ms 21776 KB Output is correct
25 Correct 525 ms 21524 KB Output is correct