oj.uz

Submission #589800

# Submission time Handle Problem Language Result Execution time Memory
589800 2022-07-05T09:42:12 Z Do_you_copy Election (BOI18_election) C++14
82 / 100
 66 ms 5852 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 1;

int n;
string s;

struct TNode{
    int pre, suf, sum, val;
    TNode operator + (TNode other){
        TNode tem;
        tem.val = max(max(val + other.sum, sum + other.val), pre + other.suf);
        tem.pre = max(pre, other.pre + sum);
        tem.suf = max(other.suf, suf + other.sum);
        tem.sum = sum + other.sum;
        return tem;
    }
};

TNode st[maxN * 4];
void build(int id = 1, int l = 1, int r = n){
    if (l == r){
        if (s[l - 1] == 'T') st[id] = {1, 1, 1, 1};
        else st[id] = {0, 0, -1, 0};

        return;
    }
    int m = (l + r) / 2;
    build(id * 2, l, m);
    build(id * 2 + 1, m + 1, r);
    st[id] = st[id * 2] + st[id * 2 + 1];
}

TNode get(int i, int j, int id = 1, int l = 1, int r = n){
    if (r < i || l > j) return {0, 0, 0, 0};
    if (i <= l && r <= j){
        return st[id];
    }
    int m = (l + r) / 2;
    return get(i, j, id * 2, l, m) + get(i, j, id * 2 + 1, m + 1, r);
}

void Init(){
    cin >> n >> s;
    int q; cin >> q;
    build();
    while (q--){
        int l, r;
        cin >> l >> r;
        cout << get(l, r).val << "\n";
    }
}


int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        //freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 47 ms 5804 KB Output is correct
7 Correct 48 ms 5720 KB Output is correct
8 Correct 52 ms 5652 KB Output is correct
9 Correct 44 ms 5696 KB Output is correct
10 Correct 49 ms 5668 KB Output is correct
11 Correct 45 ms 5840 KB Output is correct
12 Correct 50 ms 5768 KB Output is correct
13 Correct 66 ms 5852 KB Output is correct
14 Correct 65 ms 5852 KB Output is correct
15 Correct 66 ms 5712 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 47 ms 5804 KB Output is correct
7 Correct 48 ms 5720 KB Output is correct
8 Correct 52 ms 5652 KB Output is correct
9 Correct 44 ms 5696 KB Output is correct
10 Correct 49 ms 5668 KB Output is correct
11 Correct 45 ms 5840 KB Output is correct
12 Correct 50 ms 5768 KB Output is correct
13 Correct 66 ms 5852 KB Output is correct
14 Correct 65 ms 5852 KB Output is correct
15 Correct 66 ms 5712 KB Output is correct
16 Runtime error 3 ms 2408 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -