oj.uz

Submission #566052

# Submission time Handle Problem Language Result Execution time Memory
566052 2022-05-21T17:34:44 Z shrimb Election (BOI18_election) C++17
82 / 100
 68 ms 19048 KB 
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

#include"bits/stdc++.h"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;

#define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991

const int maxn = 200001;
const int N = exp2(ceil(log2(maxn)));

int Left, Right;

struct node {
    int sum;
    int mp, ms;
    int ans;
};

node operator +(const node a, const node b) {
    node c;
    c.sum = a.sum + b.sum;
    c.mp = max(a.mp, b.mp + a.sum);
    c.ms = max(b.ms, a.ms + b.sum);
    c.ans = max({a.mp + b.ms, b.ans + a.sum, a.ans + b.sum});
    return c;
}

node seg[2 * N];

node Query (int l = 1, int r = N, int ind = 1) {
    if (l > Right || r < Left) assert(0);
    if (l >= Left and r <= Right) return seg[ind];
    int m = (l + r) / 2;
    if (Left > m) return Query(m + 1, r, ind * 2 + 1);
    if (Right <= m) return Query(l, m, ind * 2);
    return Query(l, m, ind * 2) + Query(m + 1, r, ind * 2 + 1);
}

signed main () {
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    string s;
    cin >> n >> s >> q;
    for (int i = 0 ; i < n ; i++) {
        if (s[i] == 'T') {
            seg[N + i] = {1, 1, 1, 1};
        } else {
            seg[N + i] = {-1, 0, 0, 0};
        }
    }
    for (int i = N - 1 ; i ; i--) seg[i] = seg[i * 2] + seg[i * 2 + 1];
    while (q--) {
        cin >> Left >> Right;
        cout << Query().ans << endl;
    }
}

Compilation message

election.cpp:17:1: warning: multi-line comment [-Wcomment]
   17 | //\
      | ^

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8532 KB Output is correct
2 Correct 9 ms 8604 KB Output is correct
3 Correct 8 ms 8528 KB Output is correct
4 Correct 9 ms 8588 KB Output is correct
5 Correct 8 ms 8532 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8532 KB Output is correct
2 Correct 9 ms 8604 KB Output is correct
3 Correct 8 ms 8528 KB Output is correct
4 Correct 9 ms 8588 KB Output is correct
5 Correct 8 ms 8532 KB Output is correct
6 Correct 62 ms 12052 KB Output is correct
7 Correct 60 ms 11956 KB Output is correct
8 Correct 68 ms 12016 KB Output is correct
9 Correct 48 ms 12008 KB Output is correct
10 Correct 56 ms 11984 KB Output is correct
11 Correct 64 ms 12148 KB Output is correct
12 Correct 62 ms 12092 KB Output is correct
13 Correct 57 ms 12212 KB Output is correct
14 Correct 55 ms 12108 KB Output is correct
15 Correct 61 ms 12060 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8532 KB Output is correct
2 Correct 9 ms 8604 KB Output is correct
3 Correct 8 ms 8528 KB Output is correct
4 Correct 9 ms 8588 KB Output is correct
5 Correct 8 ms 8532 KB Output is correct
6 Correct 62 ms 12052 KB Output is correct
7 Correct 60 ms 11956 KB Output is correct
8 Correct 68 ms 12016 KB Output is correct
9 Correct 48 ms 12008 KB Output is correct
10 Correct 56 ms 11984 KB Output is correct
11 Correct 64 ms 12148 KB Output is correct
12 Correct 62 ms 12092 KB Output is correct
13 Correct 57 ms 12212 KB Output is correct
14 Correct 55 ms 12108 KB Output is correct
15 Correct 61 ms 12060 KB Output is correct
16 Runtime error 15 ms 19048 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -