oj.uz

답안 #760508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
760508 2023-06-17T16:44:54 Z vjudge1 Election (BOI18_election) C++17
100 / 100
 1055 ms 20388 KB 
#include <bits/stdc++.h>

using namespace std;

class Node {
    public:
	int l_max, r_max, t, ans;

};
	Node f(Node a, Node b) {
		Node r;
		r.l_max=max(a.l_max, b.l_max + a.t);
		r.r_max=max(a.r_max + b.t, b.r_max);
		r.t=a.t+b.t;
		r.ans=max(max(a.ans + b.t, b.ans + a.t), a.l_max + b.r_max);
		return r;
	}
Node v[2000001];
int n;
string s;


void build(int node=1, int l=1, int r=n) {
	if (l==r) {
		if (s[l]=='T') v[node]={1, 1, 1, 1};
		else v[node]={0, 0, -1, 0};
	} else {
		int mid=(l + r)/2;
		build(node*2, l, mid);
		build(node*2+1, mid + 1, r);
		v[node]=f(v[node*2],v[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 v[node];
	int mid=(l+r)/2;
	return f(query(a, b, node*2, l, mid),query(a, b, node*2+1, mid+1, r));

}


int main() {
	cin>>n>>s;
	s=' '+s;
	build();
	int q;
	cin>>q;
	while (q--) {
		int a, b;
		cin>>a>>b;
		cout<<query(a, b).ans<<'\n';
	}
}

Subtask #1
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct

Subtask #2
54.0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 133 ms 4820 KB Output is correct
7 Correct 134 ms 4840 KB Output is correct
8 Correct 127 ms 4772 KB Output is correct
9 Correct 123 ms 4760 KB Output is correct
10 Correct 128 ms 4700 KB Output is correct
11 Correct 129 ms 4808 KB Output is correct
12 Correct 129 ms 4888 KB Output is correct
13 Correct 131 ms 4888 KB Output is correct
14 Correct 130 ms 4768 KB Output is correct
15 Correct 129 ms 4824 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 133 ms 4820 KB Output is correct
7 Correct 134 ms 4840 KB Output is correct
8 Correct 127 ms 4772 KB Output is correct
9 Correct 123 ms 4760 KB Output is correct
10 Correct 128 ms 4700 KB Output is correct
11 Correct 129 ms 4808 KB Output is correct
12 Correct 129 ms 4888 KB Output is correct
13 Correct 131 ms 4888 KB Output is correct
14 Correct 130 ms 4768 KB Output is correct
15 Correct 129 ms 4824 KB Output is correct
16 Correct 1039 ms 19228 KB Output is correct
17 Correct 969 ms 19324 KB Output is correct
18 Correct 1004 ms 19312 KB Output is correct
19 Correct 969 ms 18820 KB Output is correct
20 Correct 1038 ms 18288 KB Output is correct
21 Correct 1030 ms 20128 KB Output is correct
22 Correct 1036 ms 19988 KB Output is correct
23 Correct 1026 ms 20388 KB Output is correct
24 Correct 1041 ms 19848 KB Output is correct
25 Correct 1055 ms 19436 KB Output is correct