oj.uz

Submission #481167

# Submission time Handle Problem Language Result Execution time Memory
481167 2021-10-19T16:43:19 Z Karabasan Election (BOI18_election) C++17
100 / 100
 1681 ms 29924 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";
    }
 
}   
 
int main()
{
    int t = 1;
    while(t--)
    {
        solve();
    }
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 6 ms 412 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 7 ms 316 KB Output is correct
6 Correct 189 ms 6020 KB Output is correct
7 Correct 182 ms 5948 KB Output is correct
8 Correct 205 ms 5940 KB Output is correct
9 Correct 170 ms 5980 KB Output is correct
10 Correct 194 ms 6152 KB Output is correct
11 Correct 199 ms 6144 KB Output is correct
12 Correct 228 ms 6120 KB Output is correct
13 Correct 197 ms 6152 KB Output is correct
14 Correct 196 ms 6072 KB Output is correct
15 Correct 204 ms 6028 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 6 ms 412 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 7 ms 316 KB Output is correct
6 Correct 189 ms 6020 KB Output is correct
7 Correct 182 ms 5948 KB Output is correct
8 Correct 205 ms 5940 KB Output is correct
9 Correct 170 ms 5980 KB Output is correct
10 Correct 194 ms 6152 KB Output is correct
11 Correct 199 ms 6144 KB Output is correct
12 Correct 228 ms 6120 KB Output is correct
13 Correct 197 ms 6152 KB Output is correct
14 Correct 196 ms 6072 KB Output is correct
15 Correct 204 ms 6028 KB Output is correct
16 Correct 1532 ms 28816 KB Output is correct
17 Correct 1557 ms 28480 KB Output is correct
18 Correct 1448 ms 28748 KB Output is correct
19 Correct 1413 ms 28308 KB Output is correct
20 Correct 1535 ms 28008 KB Output is correct
21 Correct 1642 ms 29864 KB Output is correct
22 Correct 1543 ms 29716 KB Output is correct
23 Correct 1544 ms 29924 KB Output is correct
24 Correct 1612 ms 29524 KB Output is correct
25 Correct 1681 ms 29148 KB Output is correct