oj.uz

Submission #703690

# Submission time Handle Problem Language Result Execution time Memory
703690 2023-02-28T06:33:47 Z Chal1shkan Election (BOI18_election) C++14
82 / 100
 62 ms 10120 KB 
# include <bits/stdc++.h>
 
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x  << " = " << x << endl; 
# define pll pair <ll, ll>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const ll maxn = 1e5 + 25;
const ll inf = 1e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
 
using namespace std;

ll n, q;
string s;
struct node
{
	ll pref, suff, sum, ans;
} t[maxn * 4];

node combine (node l, node r)
{
	node res;
	res.pref = max(l.pref, l.sum + r.pref);
	res.suff = max(r.suff, r.sum + l.suff);
	res.sum = l.sum + r.sum;
	res.ans = max ({l.ans + r.sum, r.ans + l.sum, l.pref + r.suff});
	return res;
}

void build (ll v = 1, ll tl = 1, ll tr = n)
{
	if (tl == tr)
	{
		ll val = max((ll)(s[tl - 1] == 'T' ? 1 : -1), 0LL);
		t[v] = {val, val, (s[tl - 1] == 'T' ? 1 : -1), val};
		return;
	}
	else
	{
		ll tm = (tl + tr) >> 1;
		build (v * 2, tl, tm);;
		build (v * 2 + 1, tm + 1, tr);
		t[v] = combine(t[v * 2], t[v * 2 + 1]);
	}
}

node get (ll l, ll r, ll v = 1, ll tl = 1, ll tr = n)
{
	if (tr < l || r < tl) return {0, 0, 0, 0};
	if (l <= tl && tr <= r) return t[v];
	ll tm = (tl + tr) >> 1;
	return combine(get(l, r, v * 2, tl, tm), get(l, r, v * 2  +1, tm + 1, tr));
}

void ma1n (/* SABR */)
{
	cin >> n >> s >> q;
	build();
	while (q--)
	{
		ll l, r;
		cin >> l >> r;
		cout << get(l, r).ans << nl;
	}
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("file.in", "r", stdin);
//  freopen("file.out", "w", stdout);
    int ttt = 1;	
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << ' ';
        ma1n();
    }
    return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 456 KB Output is correct
5 Correct 2 ms 468 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 456 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 56 ms 9804 KB Output is correct
7 Correct 52 ms 9800 KB Output is correct
8 Correct 56 ms 9824 KB Output is correct
9 Correct 60 ms 9736 KB Output is correct
10 Correct 54 ms 9772 KB Output is correct
11 Correct 61 ms 9876 KB Output is correct
12 Correct 56 ms 9924 KB Output is correct
13 Correct 55 ms 9932 KB Output is correct
14 Correct 62 ms 10120 KB Output is correct
15 Correct 58 ms 9844 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 456 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 56 ms 9804 KB Output is correct
7 Correct 52 ms 9800 KB Output is correct
8 Correct 56 ms 9824 KB Output is correct
9 Correct 60 ms 9736 KB Output is correct
10 Correct 54 ms 9772 KB Output is correct
11 Correct 61 ms 9876 KB Output is correct
12 Correct 56 ms 9924 KB Output is correct
13 Correct 55 ms 9932 KB Output is correct
14 Correct 62 ms 10120 KB Output is correct
15 Correct 58 ms 9844 KB Output is correct
16 Runtime error 3 ms 2408 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -