oj.uz

Submission #480013

# Submission time Handle Problem Language Result Execution time Memory
480013 2021-10-14T09:09:33 Z SlavicG Election (BOI18_election) C++17
100 / 100
 579 ms 29836 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 70 ms 6020 KB Output is correct
7 Correct 58 ms 5928 KB Output is correct
8 Correct 64 ms 5920 KB Output is correct
9 Correct 47 ms 5928 KB Output is correct
10 Correct 58 ms 5900 KB Output is correct
11 Correct 56 ms 6064 KB Output is correct
12 Correct 60 ms 6108 KB Output is correct
13 Correct 56 ms 6112 KB Output is correct
14 Correct 60 ms 6120 KB Output is correct
15 Correct 56 ms 6040 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 70 ms 6020 KB Output is correct
7 Correct 58 ms 5928 KB Output is correct
8 Correct 64 ms 5920 KB Output is correct
9 Correct 47 ms 5928 KB Output is correct
10 Correct 58 ms 5900 KB Output is correct
11 Correct 56 ms 6064 KB Output is correct
12 Correct 60 ms 6108 KB Output is correct
13 Correct 56 ms 6112 KB Output is correct
14 Correct 60 ms 6120 KB Output is correct
15 Correct 56 ms 6040 KB Output is correct
16 Correct 568 ms 29084 KB Output is correct
17 Correct 515 ms 28468 KB Output is correct
18 Correct 523 ms 28896 KB Output is correct
19 Correct 529 ms 28228 KB Output is correct
20 Correct 540 ms 27976 KB Output is correct
21 Correct 573 ms 29752 KB Output is correct
22 Correct 550 ms 29688 KB Output is correct
23 Correct 579 ms 29836 KB Output is correct
24 Correct 532 ms 29580 KB Output is correct
25 Correct 570 ms 29048 KB Output is correct