oj.uz

Submission #574521

# Submission time Handle Problem Language Result Execution time Memory
574521 2022-06-08T17:40:50 Z FatihSolak Election (BOI18_election) C++17
0 / 100
 2 ms 340 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;
 
struct Node {
    int l_min, r_min, tot, ans;
 
    Node operator+(Node b) {
        Node ret;
        ret.l_min = max(l_min, b.l_min - tot);
        ret.r_min = max(r_min - b.tot, b.r_min);
        ret.tot = tot + b.tot;
        ret.ans = max(max(l_min + b.ans,ans + b.r_min),l_min + b.r_min);
        return ret;
    }
};
 
Node segtree[2000001];
char s[500001];
int n;
 
void build(int node = 1, int l = 1, int r = n) {
    if (l == r) {
        if (s[l] == 'T') segtree[node] = {1, 1, -1, 1};
        else segtree[node] = {0, 0, 1, 0};
    } else {
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
        segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
    }
}
 
Node query(int a, int b, int node = 1, int l = 1, int r = n) {
    if (l > b || r < a) return {0, 0, 0, 0};
    if (l >= a && r <= b) return segtree[node];
    int mid = (l + r) / 2;
    return query(a, b, node * 2, l, mid) + query(a, b, node * 2 + 1, mid + 1, r);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef Local
		freopen("in.txt","r",stdin);
		freopen("out.txt","w",stdout);
	#endif
    cin >> n;
    FOR(i, 1, n + 1) cin >> s[i];
    build();
    int q;
    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << query(a, b).ans << '\n';
    }
    return 0;
}

Subtask #1
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -