oj.uz

Submission #571643

# Submission time Handle Problem Language Result Execution time Memory
571643 2022-06-02T12:34:18 Z nttt Election (BOI18_election) C++14
100 / 100
 590 ms 20440 KB 
#include<bits/stdc++.h>
using namespace std;
#define MASK(i) (1LL << (i))
#define BIT(x, i) ((x >> (i)) & 1)
#define fi first
#define se second
#define ll long long
#define task "name" 

const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int MOD = 1e9 + 7;
const int N = 5e5 + 3;
const int BASE = 10;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b)
{
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b)
{
    if (a < b) {a = b; return true;} return false;
}

struct nodes
{
    int sum = 0;
    int pr = 0;
    int sf = 0;
    int ans = 0;
} node[4 * N], base;
int n;
string s;
nodes add(nodes a, nodes b) 
{
	nodes c;
	c.sum = a.sum + b.sum;
	c.pr = max(a.pr, a.sum + b.pr);
	c.sf = max(b.sf, b.sum + a.sf);
	c.ans = max(a.sum + b.ans, a.ans + b.sum);
	c.ans = max(c.ans, a.pr + b.sf);
	return c;
}
void build(int id, int l, int r, int pos, int x)
{
    if(l > r || pos < l || r < pos) return;
    if (l == r) 
    {
	    node[id].sum = x;
		maximize(node[id].pr, x);
		maximize(node[id].sf, x);
		maximize(node[id].ans, x);
		return;
	}
    int mid = (l + r)/2;
	build(id * 2, l, mid, pos, x);
    build(id * 2 + 1, mid + 1, r, pos, x);
	node[id] = add(node[id * 2], node[id * 2 + 1]);
}

nodes get(int id, int l, int r, int u, int v)
{
    if (r < u || v < l) return base;
	if (u <= l && r <= v) return node[id];
    int mid = (l + r)/2;
	return add(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(task".inp" , "r" , stdin);
    //freopen(task".out" , "w" , stdout);
    
    cin >> n >> s;
    for (int i = 0; i < n; i++)
    {
        if(s[i] == 'T') build(1, 1, n, i + 1, 1);
        else build(1, 1, n, i + 1, -1);
    }
    int q;
    cin >> q;
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        cout << get(1, 1, n, l, r).ans << '\n';
    }

    return 0;
}

Subtask #1
28.0 / 28.0

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

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 420 KB Output is correct
6 Correct 58 ms 4980 KB Output is correct
7 Correct 60 ms 5012 KB Output is correct
8 Correct 80 ms 4872 KB Output is correct
9 Correct 50 ms 4824 KB Output is correct
10 Correct 59 ms 4768 KB Output is correct
11 Correct 57 ms 5004 KB Output is correct
12 Correct 62 ms 4980 KB Output is correct
13 Correct 64 ms 5048 KB Output is correct
14 Correct 55 ms 4940 KB Output is correct
15 Correct 54 ms 4948 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 420 KB Output is correct
6 Correct 58 ms 4980 KB Output is correct
7 Correct 60 ms 5012 KB Output is correct
8 Correct 80 ms 4872 KB Output is correct
9 Correct 50 ms 4824 KB Output is correct
10 Correct 59 ms 4768 KB Output is correct
11 Correct 57 ms 5004 KB Output is correct
12 Correct 62 ms 4980 KB Output is correct
13 Correct 64 ms 5048 KB Output is correct
14 Correct 55 ms 4940 KB Output is correct
15 Correct 54 ms 4948 KB Output is correct
16 Correct 524 ms 19400 KB Output is correct
17 Correct 463 ms 19512 KB Output is correct
18 Correct 534 ms 19468 KB Output is correct
19 Correct 474 ms 19188 KB Output is correct
20 Correct 541 ms 18516 KB Output is correct
21 Correct 590 ms 20284 KB Output is correct
22 Correct 517 ms 20340 KB Output is correct
23 Correct 516 ms 20440 KB Output is correct
24 Correct 530 ms 20116 KB Output is correct
25 Correct 498 ms 19632 KB Output is correct