oj.uz

Submission #61526

# Submission time Handle Problem Language Result Execution time Memory
61526 2018-07-26T06:55:10 Z koosaga(#1775) Election (BOI18_election) C++11
0 / 100
 28 ms 248 KB 
#include<bits/stdc++.h>
using namespace std;
using lint = long long;
const int MAXN = 500005;

int a[MAXN];
char str[MAXN];

struct dp{
	int low;
	int delta;
	int max;
};

dp dnc(int s, int e){
	if(s == e){
		if(str[s] == 'C'){
			return (dp){0, -1, a[e-1]};
		}
		else{
			return (dp){1, 1, a[e-1] - 1};
		}
	}
	else{
		int m = (s+e)/2;
		dp l = dnc(s, m);
		dp r = dnc(m+1, e);
		dp ret;
		ret.low = max(l.low, l.delta + r.low);
		ret.delta = l.delta + r.delta;
		ret.max = max(r.max, l.max - (r.low - l.low));
		return ret;
	}
}

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;
	}
	int q; scanf("%d",&q);
	while(q--){
		int l, r;
		scanf("%d %d",&l,&r);
		int ans = max(a[l-1] - *min_element(a+l-1, a+r+1), dnc(l, r).max - a[r]);
		printf("%d\n", ans);
	}
}

Compilation message

election.cpp: In function 'int main()':
election.cpp:37: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:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", str + 1);
  ~~~~~^~~~~~~~~~~~~~~
election.cpp:43: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:46: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
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -