oj.uz

답안 #61447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
61447 2018-07-26T03:58:25 Z ainta(#1774) Election (BOI18_election) C++11
0 / 100
 4 ms 376 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 501000
#define SZ 524288
using namespace std;
struct Tree {
	int L, R, S, M;
}IT[SZ + SZ];
int n, S[N_];
char p[N_];
Tree Merge(Tree a, Tree b) {
	return { min(a.L,a.S+b.L), min(b.R,b.S+a.R), a.S+b.S, max(max(a.M-b.S, b.M-a.S), -a.L-b.R)  };
}
void Put(int a, int b) {
	a += SZ;
	IT[a].L = IT[a].R = min(b, 0);
	IT[a].S = b;
	while (a != 1) {
		a >>= 1;
		IT[a] = Merge(IT[a * 2], IT[a * 2 + 1]);
	}
}
Tree Calc(int nd, int b, int e, int s, int l) {
	if (s > l)return { 0,0,0 };
	if (b == s&&e == l)return IT[nd];
	int m = (b + e) >> 1;
	if (s <= m && l > m) {
		return Merge(Calc(nd * 2, b, m, s, min(m, l)), Calc(nd * 2 + 1, m + 1, e, max(m + 1, s), l));
	}
	if (s <= m)return Calc(nd * 2, b, m, s, min(m, l));
	if (l > m)return Calc(nd * 2 + 1, m + 1, e, max(m + 1, s), l);
}
int main() {
	int i;

	scanf("%d", &n);
	scanf("%s", p + 1);
	S[0] = 0;
	for (i = 1; i <= n; i++) {
		if (p[i] == 'C')Put(i, 1);
		else Put(i, -1);
	}
	int Q;
	scanf("%d", &Q);
	while (Q--) {
		int b, e;
		scanf("%d%d", &b, &e);
		Tree tt = Calc(1, 0, SZ - 1, b, e);
		printf("%d\n", tt.M);
	}
}

Compilation message

election.cpp: In function 'Tree Calc(int, int, int, int, int)':
election.cpp:33:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
election.cpp: In function 'int main()':
election.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  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", p + 1);
  ~~~~~^~~~~~~~~~~~~
election.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
election.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &b, &e);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -