oj.uz

Submission #564470

# Submission time Handle Problem Language Result Execution time Memory
564470 2022-05-19T09:30:55 Z keta_tsimakuridze Election (BOI18_election) C++14
82 / 100
 90 ms 30324 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 2e5 + 5, mod = 1e9 + 7; //!
int t[N], t2[N], p[N], tree[4 * N], lazy[4 * N], ans[N];
vector<pair<int,int> > x[N];
void push(int u ,int l,int r) {
	tree[u] += lazy[u];
	if(l != r) lazy[2 * u] += lazy[u], lazy[2 * u + 1] += lazy[u];
	lazy[u] = 0;
	return;
}
void upd(int u, int st, int en, int l,int r,int v) {
	if(lazy[u]) push(u, l, r);
	if(l > en || r < st) return;
	if(st <= l && r <= en) {
		lazy[u] = v;
		push(u, l, r);
		return;
	}
	int mid = (l + r) / 2;
	upd(2 * u, st, en, l, mid, v); upd(2 * u + 1, st, en, mid + 1, r, v);
	tree[u] = max(tree[2 * u], tree[2 * u + 1]);
}
int get(int u, int st,int en, int l,int r) {
	if(lazy[u]) push(u, l, r);
	if(l > en || r < st) return -N;
	if(st <= l && r <= en) return tree[u];
	int mid = (l + r) / 2;
	return max(get(2 * u, st, en, l, mid), get(2 * u + 1, st, en, mid + 1, r));	
}
void upd(int id, int val) {
	for(id; id >= 1; id -= id & (-id)) t[id] += val;
}	int n;
int get(int id) {
	int ans = 0;
	for(id; id <= n; id += id & (-id)) ans += t[id];
	return ans;
}
void UPD(int id, int val) {
	for(id; id >= 1; id -= id & (-id)) t2[id] += val;
}
int GET(int id) {
	int ans = 0;
	for(id; id <= n; id += id & (-id)) ans += t2[id];
	return ans;
}
main() {
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	cin >> n;
	for(int i = 1; i <= n; i++) {
		char c; cin >> c;
		p[i] = p[i - 1] + (c == 'T' ? 1 : -1);
		upd(1, 1, i, 1, n, p[i] - p[i - 1]);
		upd(i, p[i] - p[i - 1]);
	}
	int q; cin >> q;
	for(int i = 1; i <= q; i++) {
		int l, r;
		cin >> l >> r;
		x[l].push_back({i, r});
	}
	
	vector<int> v;
	int l = 0;
	for(int i = n; i >= 1; i--) {
		while(v.size() && p[v.back()] <= p[i]) {
			if(l == v.size()) {
				l--;
				upd(v.back(), 1);
				UPD(v.back(), -1);
				upd(1,1, v.back(), 1, n, 1);
			}
			v.pop_back();
		}
		v.push_back(i);
		while(l < v.size() && p[v[l]] - p[i - 1] > 0)  upd(1, 1, v[l], 1, n, -1), upd(v[l], -1), UPD(v[l], 1),  ++l;
		while(l > 0 && p[v[l - 1]] - p[i - 1] <= 0) upd(1, 1, v[l - 1], 1, n, 1), upd(v[l - 1], 1), UPD(v[l - 1], -1), --l;
		if(x[i].size()) {

		} else continue;
		for(int j = 0; j < x[i].size(); j++) {
			ans[x[i][j].f] = max(0ll, get(1, i, x[i][j].s, 1, n) -  get(x[i][j].s + 1)) + GET(i) - GET(x[i][j].s + 1);
		}
	}
	
	for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}

Compilation message

election.cpp: In function 'void upd(long long int, long long int)':
election.cpp:37:6: warning: statement has no effect [-Wunused-value]
   37 |  for(id; id >= 1; id -= id & (-id)) t[id] += val;
      |      ^~
election.cpp: In function 'long long int get(long long int)':
election.cpp:41:6: warning: statement has no effect [-Wunused-value]
   41 |  for(id; id <= n; id += id & (-id)) ans += t[id];
      |      ^~
election.cpp: In function 'void UPD(long long int, long long int)':
election.cpp:45:6: warning: statement has no effect [-Wunused-value]
   45 |  for(id; id >= 1; id -= id & (-id)) t2[id] += val;
      |      ^~
election.cpp: In function 'long long int GET(long long int)':
election.cpp:49:6: warning: statement has no effect [-Wunused-value]
   49 |  for(id; id <= n; id += id & (-id)) ans += t2[id];
      |      ^~
election.cpp: At global scope:
election.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main() {
      | ^~~~
election.cpp: In function 'int main()':
election.cpp:73:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |    if(l == v.size()) {
      |       ~~^~~~~~~~~~~
election.cpp:82:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   while(l < v.size() && p[v[l]] - p[i - 1] > 0)  upd(1, 1, v[l], 1, n, -1), upd(v[l], -1), UPD(v[l], 1),  ++l;
      |         ~~^~~~~~~~~~
election.cpp:87:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(int j = 0; j < x[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 4 ms 5164 KB Output is correct
3 Correct 4 ms 5172 KB Output is correct
4 Correct 5 ms 5204 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 4 ms 5164 KB Output is correct
3 Correct 4 ms 5172 KB Output is correct
4 Correct 5 ms 5204 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct
6 Correct 89 ms 14392 KB Output is correct
7 Correct 77 ms 14292 KB Output is correct
8 Correct 88 ms 14096 KB Output is correct
9 Correct 90 ms 14248 KB Output is correct
10 Correct 83 ms 14248 KB Output is correct
11 Correct 87 ms 14724 KB Output is correct
12 Correct 87 ms 14456 KB Output is correct
13 Correct 87 ms 14756 KB Output is correct
14 Correct 88 ms 14384 KB Output is correct
15 Correct 80 ms 14284 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 4 ms 5164 KB Output is correct
3 Correct 4 ms 5172 KB Output is correct
4 Correct 5 ms 5204 KB Output is correct
5 Correct 5 ms 5204 KB Output is correct
6 Correct 89 ms 14392 KB Output is correct
7 Correct 77 ms 14292 KB Output is correct
8 Correct 88 ms 14096 KB Output is correct
9 Correct 90 ms 14248 KB Output is correct
10 Correct 83 ms 14248 KB Output is correct
11 Correct 87 ms 14724 KB Output is correct
12 Correct 87 ms 14456 KB Output is correct
13 Correct 87 ms 14756 KB Output is correct
14 Correct 88 ms 14384 KB Output is correct
15 Correct 80 ms 14284 KB Output is correct
16 Runtime error 66 ms 30324 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -