oj.uz

Submission #598280

# Submission time Handle Problem Language Result Execution time Memory
598280 2022-07-17T22:13:58 Z AlesL0 Election (BOI18_election) C++17
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segtree {
    ll sum, left, right, range;
};

vector <segtree> T;
ll k = 1;
vector <ll> sol;

const ll ZERO = 0;

void build(vector <ll> a){
    ll n = a.size();
    while (k < n)k *= 2;
    T.resize(2*k);
    for (int i = 0; i < n; i++)T[i+k] = {a[i], max(a[i], ZERO), max(a[i], ZERO), i};
    for (int i = n; i < k; i++)T[i+k] = {0, 0, 0, i};
    for (int i = k-1; i; i--)T[i] = {T[2*i].sum+T[2*i+1].sum, max(T[2*i].sum+T[2*i+1].left, T[2*i].left), max(T[2*i].right+T[2*i+1].sum, T[2*i+1].right), T[2*i].range};
}

void range_query(ll i, ll x, ll y, ll l, ll r){
    if (l >= x && r <= y){sol.push_back(i); return;}
    if (l >= y || r <= x)return;
    range_query(2*i, x, y, l, (l+r)>>1); 
    range_query(2*i+1, x, y, (l+r)>>1, r);
}

bool cmp(ll a, ll b){
    return (T[a].range < T[b].range);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll n; cin >> n;
    string s; cin >> s;
    vector <ll> a(n, 1);
    for (int i = 0; i < n; i++)if (s[i] == 'C')a[i] = -1;
    build(a);
    ll q; cin >> q;
    while (q--){
        ll l, r; cin >> l >> r;
        l--; r--;
        range_query(1, l, r+1, 0, k);
        sort(sol.begin(), sol.end(), cmp);
        ll sum = 0;
        r = 0;
        for (auto i : sol){
            r = max(r, sum+T[i].left);
            sum += T[i].sum;
        }
        sum = 0;
        for (int j = sol.size()-1; j >= 0; j--){
            ll i = sol[j];
            r = max(r, sum+T[i].right);
            sum += T[i].sum;
        }
        cout << r << "\n";
        sol.clear();
    }
}

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -