oj.uz

Submission #348611

# Submission time Handle Problem Language Result Execution time Memory
348611 2021-01-15T09:34:59 Z parsabahrami Election (BOI18_election) C++17
100 / 100
 663 ms 21740 KB 
// 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

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.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 68 ms 5740 KB Output is correct
7 Correct 61 ms 5740 KB Output is correct
8 Correct 62 ms 5612 KB Output is correct
9 Correct 58 ms 5612 KB Output is correct
10 Correct 66 ms 5612 KB Output is correct
11 Correct 73 ms 5740 KB Output is correct
12 Correct 66 ms 5888 KB Output is correct
13 Correct 69 ms 5868 KB Output is correct
14 Correct 68 ms 5996 KB Output is correct
15 Correct 70 ms 5740 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 68 ms 5740 KB Output is correct
7 Correct 61 ms 5740 KB Output is correct
8 Correct 62 ms 5612 KB Output is correct
9 Correct 58 ms 5612 KB Output is correct
10 Correct 66 ms 5612 KB Output is correct
11 Correct 73 ms 5740 KB Output is correct
12 Correct 66 ms 5888 KB Output is correct
13 Correct 69 ms 5868 KB Output is correct
14 Correct 68 ms 5996 KB Output is correct
15 Correct 70 ms 5740 KB Output is correct
16 Correct 656 ms 20588 KB Output is correct
17 Correct 536 ms 20716 KB Output is correct
18 Correct 597 ms 20860 KB Output is correct
19 Correct 515 ms 20460 KB Output is correct
20 Correct 653 ms 19772 KB Output is correct
21 Correct 663 ms 21740 KB Output is correct
22 Correct 648 ms 21356 KB Output is correct
23 Correct 652 ms 21740 KB Output is correct
24 Correct 644 ms 21228 KB Output is correct
25 Correct 651 ms 20880 KB Output is correct