Submission #348611

#	Time	Username	Problem	Language	Result	Execution time	Memory
348611		parsabahrami	Election (BOI18_election)	C++17	100 / 100	663 ms	21740 KiB

election

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second
#define lc                          id << 1
#define rc                          lc | 1

const int N = 5e5 + 10, MOD = 1e9 + 7;
struct Nude {
    int pre, suff, ret, sum;

    friend Nude operator+(Nude x, Nude y) {
        if (x.ret == -MOD) return y;
        if (y.ret == -MOD) return x;
        return {max(x.pre, y.pre + x.sum), max(y.suff, x.suff + y.sum), max({x.pre + y.suff, y.ret + x.sum, x.ret + y.sum}), x.sum + y.sum};
    }
};

Nude seg[N << 2];
int n, q; char S[N];

void build(int id = 1, int l = 1, int r = n + 1) {
    if (r - l < 2) {
        if (S[l] == 'T') seg[id] = {1, 1, 1, 1};
        else seg[id] = {0, 0, 0, -1};
        return;
    }
    int mid = (l + r) >> 1;
    build(lc, l, mid);
    build(rc, mid, r);
    seg[id] = seg[lc] + seg[rc];
}

Nude get(int ql, int qr, int id = 1, int l = 1, int r = n + 1) {
    if (qr <= l || r <= ql) return {-MOD, -MOD, -MOD, -MOD};
    if (ql <= l && r <= qr) return seg[id];
    int mid = (l + r) >> 1;
    return get(ql, qr, lc, l, mid) + get(ql, qr, rc, mid, r);
}

int main() {
    scanf("%d%s", &n, S + 1);
    build();
    for (scanf("%d", &q); q; q--) {
        int l, r; scanf("%d%d", &l, &r);
        printf("%d\n", get(l, r + 1).ret);
    }
    return 0;
}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |     scanf("%d%s", &n, S + 1);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
election.cpp:51:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |     for (scanf("%d", &q); q; q--) {
      |          ~~~~~^~~~~~~~~~
election.cpp:52:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         int l, r; scanf("%d%d", &l, &r);
      |                   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18