oj.uz

Submission #61539

# Submission time Handle Problem Language Result Execution time Memory
61539 2018-07-26T07:21:56 Z koosaga(#1775) Election (BOI18_election) C++11
82 / 100
 3000 ms 52496 KB 
#include<bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using lint = long long;
const int MAXN = 500005;
const int MAXT = 1050000;

int a[MAXN], nxt[19][MAXN], edg[19][MAXN];
char str[MAXN];
vector<pi> v;

struct seg{
	int tree[MAXT], lim;
	void init(int n, int *a){
		for(lim = 1; lim <= n; lim <<= 1);
		fill(tree, tree + MAXT, -1e9);
		for(int i=0; i<n; i++) tree[i + lim] = a[i];
		for(int i=lim-1; i; i--) tree[i] = max(tree[2*i], tree[2*i+1]);
	}
	int query(int s, int e){
		s += lim;
		e += lim;
		int ret = -1e9;
		while(s < e){
			if(s % 2 == 1) ret = max(ret, tree[s++]);
			if(e % 2 == 0) ret = max(ret, tree[e--]);
			s >>= 1;
			e >>= 1;
		}
		if(s == e) ret = max(ret, tree[s]);
		return ret;
	}
}seg;

int main(){
	int n; scanf("%d",&n);
	scanf("%s", str + 1);
	for(int i=1; i<=n; i++){
		if(str[i] == 'C') a[i] = a[i-1] + 1;
		else a[i] = a[i-1] - 1;
	}
	seg.init(n + 1, a);
	for(int i=0; i<=n; i++) v.push_back(pi(a[i], i));
	sort(v.begin(), v.end());
	for(int i=0; i<=n; i++){
		auto k = lower_bound(v.begin(), v.end(), pi(a[i] - 1, i));
		if(k == v.end() || k->first != a[i] - 1){
			nxt[0][i] = n + 1;
			edg[0][i] = -1e9;
		}
		else{
			nxt[0][i] = k->second;
			edg[0][i] = seg.query(i, nxt[0][i] - 1);
		}
	}
	nxt[0][n+1] = n+1;
	edg[0][n+1] = -1e9;
	for(int i=1; i<19; i++){
		for(int j=n+1; j>=0; j--){
			nxt[i][j] = nxt[i-1][nxt[i-1][j]];
		}
	}
	int q; scanf("%d",&q);
	while(q--){
		int l, r;
		scanf("%d %d",&l,&r);
		l--;
		int dap = -1e9;
		int cnt = 0;
		while(nxt[0][l] <= r){
			cnt++;
			dap = max(dap - 1, edg[0][l]);
			l = nxt[0][l];
		}
		dap = max(dap - 1, seg.query(l, r));
		printf("%d\n", cnt + dap - a[r]);
	}
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n; scanf("%d",&n);
         ~~~~~^~~~~~~~~
election.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", str + 1);
  ~~~~~^~~~~~~~~~~~~~~
election.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int q; scanf("%d",&q);
         ~~~~~^~~~~~~~~
election.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&l,&r);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4728 KB Output is correct
2 Correct 8 ms 4836 KB Output is correct
3 Correct 8 ms 4928 KB Output is correct
4 Correct 11 ms 5004 KB Output is correct
5 Correct 9 ms 5004 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4728 KB Output is correct
2 Correct 8 ms 4836 KB Output is correct
3 Correct 8 ms 4928 KB Output is correct
4 Correct 11 ms 5004 KB Output is correct
5 Correct 9 ms 5004 KB Output is correct
6 Correct 124 ms 11740 KB Output is correct
7 Correct 123 ms 11740 KB Output is correct
8 Correct 93 ms 11740 KB Output is correct
9 Correct 96 ms 11740 KB Output is correct
10 Correct 92 ms 11740 KB Output is correct
11 Correct 889 ms 11796 KB Output is correct
12 Correct 552 ms 11796 KB Output is correct
13 Correct 1430 ms 11800 KB Output is correct
14 Correct 476 ms 11808 KB Output is correct
15 Correct 166 ms 11808 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4728 KB Output is correct
2 Correct 8 ms 4836 KB Output is correct
3 Correct 8 ms 4928 KB Output is correct
4 Correct 11 ms 5004 KB Output is correct
5 Correct 9 ms 5004 KB Output is correct
6 Correct 124 ms 11740 KB Output is correct
7 Correct 123 ms 11740 KB Output is correct
8 Correct 93 ms 11740 KB Output is correct
9 Correct 96 ms 11740 KB Output is correct
10 Correct 92 ms 11740 KB Output is correct
11 Correct 889 ms 11796 KB Output is correct
12 Correct 552 ms 11796 KB Output is correct
13 Correct 1430 ms 11800 KB Output is correct
14 Correct 476 ms 11808 KB Output is correct
15 Correct 166 ms 11808 KB Output is correct
16 Correct 1505 ms 52376 KB Output is correct
17 Correct 791 ms 52496 KB Output is correct
18 Correct 1126 ms 52496 KB Output is correct
19 Correct 1267 ms 52496 KB Output is correct
20 Correct 812 ms 52496 KB Output is correct
21 Execution timed out 3053 ms 52496 KB Time limit exceeded
22 Halted 0 ms 0 KB -