oj.uz

Submission #61661

# Submission time Handle Problem Language Result Execution time Memory
61661 2018-07-26T09:50:45 Z gs14004 Election (BOI18_election) C++17
100 / 100
 1841 ms 88572 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]];
			edg[i][j] = max(edg[i-1][j] - (1<<(i-1)), edg[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;
		for(int i=18; i>=0; i--){
			if(nxt[i][l] <= r){
				cnt += (1<<i);
				dap = max(dap - (1<<i), edg[i][l]);
				l = nxt[i][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:64: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:67: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 9 ms 5112 KB Output is correct
2 Correct 11 ms 5112 KB Output is correct
3 Correct 9 ms 5316 KB Output is correct
4 Correct 9 ms 5316 KB Output is correct
5 Correct 9 ms 5324 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5112 KB Output is correct
2 Correct 11 ms 5112 KB Output is correct
3 Correct 9 ms 5316 KB Output is correct
4 Correct 9 ms 5316 KB Output is correct
5 Correct 9 ms 5324 KB Output is correct
6 Correct 151 ms 16600 KB Output is correct
7 Correct 106 ms 16640 KB Output is correct
8 Correct 122 ms 16696 KB Output is correct
9 Correct 114 ms 16696 KB Output is correct
10 Correct 136 ms 16696 KB Output is correct
11 Correct 142 ms 16724 KB Output is correct
12 Correct 126 ms 16800 KB Output is correct
13 Correct 145 ms 16928 KB Output is correct
14 Correct 110 ms 16928 KB Output is correct
15 Correct 120 ms 16928 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5112 KB Output is correct
2 Correct 11 ms 5112 KB Output is correct
3 Correct 9 ms 5316 KB Output is correct
4 Correct 9 ms 5316 KB Output is correct
5 Correct 9 ms 5324 KB Output is correct
6 Correct 151 ms 16600 KB Output is correct
7 Correct 106 ms 16640 KB Output is correct
8 Correct 122 ms 16696 KB Output is correct
9 Correct 114 ms 16696 KB Output is correct
10 Correct 136 ms 16696 KB Output is correct
11 Correct 142 ms 16724 KB Output is correct
12 Correct 126 ms 16800 KB Output is correct
13 Correct 145 ms 16928 KB Output is correct
14 Correct 110 ms 16928 KB Output is correct
15 Correct 120 ms 16928 KB Output is correct
16 Correct 1077 ms 87512 KB Output is correct
17 Correct 865 ms 87644 KB Output is correct
18 Correct 868 ms 87720 KB Output is correct
19 Correct 955 ms 87720 KB Output is correct
20 Correct 1022 ms 87720 KB Output is correct
21 Correct 1841 ms 88336 KB Output is correct
22 Correct 1259 ms 88336 KB Output is correct
23 Correct 1418 ms 88572 KB Output is correct
24 Correct 1289 ms 88572 KB Output is correct
25 Correct 1163 ms 88572 KB Output is correct