oj.uz

Submission #244645

# Submission time Handle Problem Language Result Execution time Memory
244645 2020-07-04T13:28:36 Z bibabas Election (BOI18_election) C++14
0 / 100
 23 ms 512 KB 
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
 
#define ll long long
#define ull unsigned ll
#define vi vector<ll>
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define ld long double
#define pii pair<ll, ll>
#define mt make_tuple
#define mn(a, b) a = min(a, b)
#define mx(a, b) a = max(a, b)
 
using namespace std;
 
const ll INF = (ll)2e9;
const ll inf = (ll)2e18;
const ld eps = (ld)1e-8;
const ll mod = (ll)998244353;
const ll MAXN = (ll)1e5 + 1;
const ll MAXC = (ll)1e6 + 1;
const ll MAXE = (ll)1000;
const ll MAXLOG = 21;
const ll maxlen = (ll)1e5;
const ll asci = (ll)256;
const ll block = 480;
const ld PI = acos(-1);
const ld e = 2.7182818284;
 
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<
pii,
null_type,
less<pii>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;*/
 
template <class T>
istream& operator >>(istream &in, vector<T> &arr){
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
};

struct stree{
    vi t; int n;

    void build(int v, int tl, int tr, vi &a) {
        if (tl + 1 == tr) return void (t[v] = a[tl]);
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm, a);
        build(2 * v + 1, tm, tr, a);
        t[v] = min(t[2 * v], t[2 * v + 1]);
    }

    stree(vi &a): n(a.size()) {
        t.resize(4 * n);
        build(1, 0, n, a);
    }

    int ask(int v, int tl, int tr, int l, int r) {
        if (l <= tl && tr <= r) return t[v];
        if (tl >= r || l >= tr) return INF;
        int tm = (tl + tr) / 2;
        return min(ask(2 * v, tl, tm, l, r), ask(2 * v + 1, tm, tr, l, r));
    }
};

int val(int Ls, int Rs, int pos, stree &t_pref, stree &t_suf, vi &pref, vi &suf, int n) {
    return max({0LL, pref[Ls + 1] - t_pref.ask(1, 0, n + 1, Ls + 1, pos + 1), suf[Rs + 1] - t_suf.ask(1, 0, n + 1, pos + 1, Rs + 2)});
}

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    vi a(n);
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'C') a[i]++;
        else a[i]--;
    }
    vi pref(n + 1), suf(n + 1);
    for (int i = 0; i < n; ++i) {
        pref[i + 1] = pref[i] + a[i];
    }
    for (int i = n - 1; i > -1; --i) {
        suf[i] = suf[i + 1] + a[i];
    }
    stree t_pref(pref), t_suf(suf);
    int q; cin >> q;
    while (q--) {
        int Ls, Rs; cin >> Ls >> Rs;
        Ls -= 2, Rs--;
        int L = Ls, R = Rs;
        while (R - L > 2) {
            int midl = L + (R - L) / 3;
            int midr = R - (R - L) / 3;
            if (val(Ls, Rs, midl, t_pref, t_suf, pref, suf, n) >= val(Ls, Rs, midr, t_pref, t_suf, pref, suf, n)) R = midr;
            else L = midl;
        }
        cout << max({val(Ls, Rs, L, t_pref, t_suf, pref, suf, n), L + 1 <= R ? val(Ls, Rs, L + 1, t_pref, t_suf, pref, suf, n) : 0, L + 2 <= R ? val(Ls, Rs, L + 2, t_pref, t_suf, pref, suf, n) : 0}) << "\n";
    }
}

int main() {
    srand(time(0));
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#endif
    cout.precision(30);
    
    solve();
 
    return 0;
}

Subtask #1
0 / 28.0

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

Subtask #2
0 / 54.0

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

Subtask #3
0 / 18.0

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