oj.uz

Submission #61537

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

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

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;
	}
	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[i] = 1e9;
		else{
			nxt[i] = k->second;
		}
	}
	int q; scanf("%d",&q);
	while(q--){
		int l, r;
		scanf("%d %d",&l,&r);
		l--;
		int dap = -1e9;
		int cnt = 0;
		while(nxt[l] <= r){
			cnt++;
			dap = max(dap - 1, *max_element(a + l, a + nxt[l]));
			l = nxt[l];
		}
		dap = max(dap - 1, *max_element(a + l, a + r + 1));
		printf("%d\n", cnt + dap - a[r]);
	}
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:12: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:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", str + 1);
  ~~~~~^~~~~~~~~~~~~~~
election.cpp:27: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:30: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 6 ms 408 KB Output is correct
2 Correct 5 ms 408 KB Output is correct
3 Correct 5 ms 540 KB Output is correct
4 Correct 7 ms 540 KB Output is correct
5 Correct 6 ms 540 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 408 KB Output is correct
2 Correct 5 ms 408 KB Output is correct
3 Correct 5 ms 540 KB Output is correct
4 Correct 7 ms 540 KB Output is correct
5 Correct 6 ms 540 KB Output is correct
6 Correct 1447 ms 2152 KB Output is correct
7 Execution timed out 3015 ms 2152 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 408 KB Output is correct
2 Correct 5 ms 408 KB Output is correct
3 Correct 5 ms 540 KB Output is correct
4 Correct 7 ms 540 KB Output is correct
5 Correct 6 ms 540 KB Output is correct
6 Correct 1447 ms 2152 KB Output is correct
7 Execution timed out 3015 ms 2152 KB Time limit exceeded
8 Halted 0 ms 0 KB -