oj.uz

Submission #730254

# Submission time Handle Problem Language Result Execution time Memory
730254 2023-04-25T14:06:15 Z nguyentunglam Election (BOI18_election) C++17
100 / 100
 834 ms 121952 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 5e5 + 10;
int a[N], b[N], s[N], last[N << 1], S[20][N], f[20][N], g[20][N], lg[N];
int get(int l, int r) {
    int k = lg[r - l + 1];
    return max(S[k][l], S[k][r - (1 << k) + 1]);
}
int main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int n; cin >> n;
    string str; cin >> str; str = " " + str;
    for(int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;

    for(int i = 1; i <= n; i++) {
        a[i] = str[i] == 'C' ? 1 : -1;
        s[i] = s[i - 1] + a[i];
        S[0][i] = s[i];
    }

    for(int j = 1; j <= lg[n]; j++) for(int i = 0; i + (1 << j) - 1 <= n; i++) {
        S[j][i] = max(S[j - 1][i], S[j - 1][i + (1 << j >> 1)]);
    }

    for(int i = n; i >= 1; i--) {
        last[s[i] + n] = i;
        f[0][i] = last[s[i - 1] - 1 + n];
        int pos = f[0][i];
        if (i <= pos) g[0][i] = s[pos] - get(i - 1, pos - 1) + 1;
//        cout << i << " " << f[0][i] << " " << g[0][i] << endl;
    }

    for(int j = 1; j <= lg[n]; j++) for(int i = 1; i <= n; i++) {
        int pos = f[j - 1][i] + 1;
        if (!f[j - 1][i]) continue;
        f[j][i] = f[j - 1][pos];
        g[j][i] = min(g[j - 1][i], g[j - 1][pos]);
    }

    int q; cin >> q;
    while (q--) {
        int l, r; cin >> l >> r;
        int last = l - 1, suffix = 0, ans = 0;
        for(int j = lg[n]; j >= 0; j--) if (f[j][last + 1] && f[j][last + 1] <= r) {
            suffix = min(suffix, g[j][last + 1]);
            last = f[j][last + 1];
            ans += (1 << j);
        }
        if (last < r) {
            suffix += s[r] - s[last];
            suffix = min(suffix, 0);
            suffix = min(suffix, s[r] - get(last, r - 1));
        }
        cout << ans - suffix << endl;
    }
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:17:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:18:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:21:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election.cpp:22:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 50 ms 11236 KB Output is correct
7 Correct 29 ms 10940 KB Output is correct
8 Correct 38 ms 10744 KB Output is correct
9 Correct 36 ms 11208 KB Output is correct
10 Correct 32 ms 9652 KB Output is correct
11 Correct 52 ms 14720 KB Output is correct
12 Correct 46 ms 14028 KB Output is correct
13 Correct 52 ms 15096 KB Output is correct
14 Correct 37 ms 13324 KB Output is correct
15 Correct 37 ms 11716 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 50 ms 11236 KB Output is correct
7 Correct 29 ms 10940 KB Output is correct
8 Correct 38 ms 10744 KB Output is correct
9 Correct 36 ms 11208 KB Output is correct
10 Correct 32 ms 9652 KB Output is correct
11 Correct 52 ms 14720 KB Output is correct
12 Correct 46 ms 14028 KB Output is correct
13 Correct 52 ms 15096 KB Output is correct
14 Correct 37 ms 13324 KB Output is correct
15 Correct 37 ms 11716 KB Output is correct
16 Correct 473 ms 90108 KB Output is correct
17 Correct 251 ms 85364 KB Output is correct
18 Correct 367 ms 86468 KB Output is correct
19 Correct 325 ms 91840 KB Output is correct
20 Correct 378 ms 71028 KB Output is correct
21 Correct 834 ms 118352 KB Output is correct
22 Correct 482 ms 104104 KB Output is correct
23 Correct 609 ms 121952 KB Output is correct
24 Correct 490 ms 101128 KB Output is correct
25 Correct 392 ms 80468 KB Output is correct