oj.uz

Submission #865475

# Submission time Handle Problem Language Result Execution time Memory
865475 2023-10-24T09:01:22 Z farica Election (BOI18_election) C++14
100 / 100
 1231 ms 28328 KB 
#include <bits/stdc++.h>
#define long long ll

using namespace std;

const int MAX_N=1e6;

struct Node {
    int sum, pref, suf, ans;
    Node operator+(Node b) {
		Node ret;
		ret.sum = sum + b.sum;
        ret.pref = max(pref, b.pref + sum);
        ret.suf = max(b.suf, suf + b.sum);
        ret.ans = max(max(ans + b.sum, b.ans + sum), pref + b.suf);
		return ret;
	}

};

string s;
Node seg[4*MAX_N];
int L,R;

void build(int node, int l, int r) {
    if(l==r) {
        if(s[l]=='T') seg[node].sum = seg[node].ans = seg[node].pref = seg[node].suf = 1;
        else {
            seg[node].sum = -1;
            seg[node].pref = seg[node].suf = seg[node].ans = 0;
        }
        return;
    }
    int m = (l+r)/2;
    build(2*node, l, m);
    build(2*node+1, m+1, r);
    seg[node] = seg[2*node] + seg[2*node+1];
}

Node check(int node, int l, int r) {
    if(l>R or r<L) return {0, 0, 0, 0};
    if(l>=L && r<=R) return seg[node];
    else return check(2*node, l, (l+r)/2) + check(2*node+1, (l+r)/2+1, r);
}

void solve() {
    int n;
    cin >> n;
    cin >> s;
    int q;
    cin >> q;
    build(1, 0, n-1);
    while(q--) {
        int l,r;
        cin >> l >> r;
        --l, --r;
        L=l, R=r;
        cout << check(1, 0, n-1).ans << endl;
    }
}

int main()
{
    int T=1;
    while(T--) solve();

    return 0;
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 4 ms 452 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 133 ms 6028 KB Output is correct
7 Correct 131 ms 5968 KB Output is correct
8 Correct 131 ms 5872 KB Output is correct
9 Correct 128 ms 5784 KB Output is correct
10 Correct 133 ms 5868 KB Output is correct
11 Correct 132 ms 5968 KB Output is correct
12 Correct 136 ms 5972 KB Output is correct
13 Correct 132 ms 6028 KB Output is correct
14 Correct 142 ms 6080 KB Output is correct
15 Correct 133 ms 5968 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 348 KB Output is correct
2 Correct 4 ms 452 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 133 ms 6028 KB Output is correct
7 Correct 131 ms 5968 KB Output is correct
8 Correct 131 ms 5872 KB Output is correct
9 Correct 128 ms 5784 KB Output is correct
10 Correct 133 ms 5868 KB Output is correct
11 Correct 132 ms 5968 KB Output is correct
12 Correct 136 ms 5972 KB Output is correct
13 Correct 132 ms 6028 KB Output is correct
14 Correct 142 ms 6080 KB Output is correct
15 Correct 133 ms 5968 KB Output is correct
16 Correct 1124 ms 27356 KB Output is correct
17 Correct 999 ms 26764 KB Output is correct
18 Correct 1016 ms 27148 KB Output is correct
19 Correct 985 ms 26600 KB Output is correct
20 Correct 1039 ms 26680 KB Output is correct
21 Correct 1044 ms 28328 KB Output is correct
22 Correct 1079 ms 27848 KB Output is correct
23 Correct 1109 ms 28240 KB Output is correct
24 Correct 1231 ms 28096 KB Output is correct
25 Correct 1133 ms 27380 KB Output is correct