oj.uz

Submission #758260

# Submission time Handle Problem Language Result Execution time Memory
758260 2023-06-14T10:20:08 Z LucaIlie Election (BOI18_election) C++17
100 / 100
 1254 ms 29460 KB 
#include <bits/stdc++.h>

using namespace std;

struct info {
    int elim, sum, minPref, minSuf;

    info operator + ( const info &r ) const {
        info l = *this;
        info ans;

        ans.elim = max( -l.minPref + -r.minSuf, max( l.elim - r.sum, r.elim - l.sum ) );
        ans.sum = l.sum + r.sum;
        ans.minPref = min( l.minPref, l.sum + r.minPref );
        ans.minSuf = min( r.minSuf, r.sum + l.minSuf );

        return ans;
    }
};

const int MAX_N = 5e5;
int vote[MAX_N + 1];
info segTree[4 * MAX_N];

void init( int v, int l, int r ) {
    if ( l == r ) {
        segTree[v] = { (vote[l] == -1), vote[l], -(vote[l] == -1), -(vote[l] == -1) };
        return;
    }
    int mid = (l + r) / 2;
    init( v * 2 + 1, l, mid );
    init( v * 2 + 2, mid + 1, r );
    segTree[v] = segTree[v * 2 + 1] + segTree[v * 2 + 2];
}

info query( int v, int l, int r, int lq, int rq ) {
    if ( lq <= l && r <= rq )
        return segTree[v];

    int mid = (l + r) / 2;
    if ( mid + 1 > rq )
        return query( v * 2 + 1, l, mid, lq, rq );
    if ( mid < lq )
        return query( v * 2 + 2, mid + 1, r, lq, rq );
    return query( v * 2 + 1, l, mid, lq, rq ) + query( v * 2 + 2, mid + 1, r, lq, rq );
}

int main() {
    int n, q;

    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        char ch;
        cin >> ch;
        vote[i] = (ch == 'C' ? 1 : -1);
    }

    init( 0, 1, n );

    cin >> q;
    for ( int i = 0; i < q; i++ ) {
        int l, r;
        cin >> l >> r;
        cout << query( 0, 1, n, l, r ).elim << "\n";
    }

    return 0;
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 165 ms 5880 KB Output is correct
7 Correct 155 ms 5752 KB Output is correct
8 Correct 155 ms 5728 KB Output is correct
9 Correct 142 ms 5716 KB Output is correct
10 Correct 152 ms 5732 KB Output is correct
11 Correct 164 ms 5836 KB Output is correct
12 Correct 158 ms 5992 KB Output is correct
13 Correct 161 ms 5980 KB Output is correct
14 Correct 162 ms 5992 KB Output is correct
15 Correct 162 ms 5896 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 5 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 165 ms 5880 KB Output is correct
7 Correct 155 ms 5752 KB Output is correct
8 Correct 155 ms 5728 KB Output is correct
9 Correct 142 ms 5716 KB Output is correct
10 Correct 152 ms 5732 KB Output is correct
11 Correct 164 ms 5836 KB Output is correct
12 Correct 158 ms 5992 KB Output is correct
13 Correct 161 ms 5980 KB Output is correct
14 Correct 162 ms 5992 KB Output is correct
15 Correct 162 ms 5896 KB Output is correct
16 Correct 1219 ms 28240 KB Output is correct
17 Correct 1191 ms 28080 KB Output is correct
18 Correct 1216 ms 28172 KB Output is correct
19 Correct 1160 ms 27828 KB Output is correct
20 Correct 1254 ms 27488 KB Output is correct
21 Correct 1233 ms 29412 KB Output is correct
22 Correct 1210 ms 29160 KB Output is correct
23 Correct 1206 ms 29460 KB Output is correct
24 Correct 1218 ms 29052 KB Output is correct
25 Correct 1223 ms 28448 KB Output is correct