Submission #730254

#	Time	Username	Problem	Language	Result	Execution time	Memory
730254		nguyentunglam	Election (BOI18_election)	C++17	100 / 100	834 ms	121952 KiB

election

#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 (stderr)

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 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18