Submission #65368008

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
int N;
int A[212345];
int Q;
int L[212345], R[212345];
long long sum[212345];
int main(void) {
  int i;
  if (scanf("%d", &N) != 1) return 1;
  for (i = 1; i <= N; i++) {
    if (scanf("%d", &A[i]) != 1) return 1;
  }
  if (scanf("%d", &Q) != 1) return 1;
  for (i = 0; i < Q; i++) {
    if (scanf("%d%d", &L[i], &R[i]) != 2) return 1;
  }
  for (i = 1; i <= N; i++) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

int N;
int A[212345];
int Q;
int L[212345], R[212345];

long long sum[212345];

int main(void) {
	int i;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 1; i <= N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	if (scanf("%d", &Q) != 1) return 1;
	for (i = 0; i < Q; i++) {
		if (scanf("%d%d", &L[i], &R[i]) != 2) return 1;
	}

	for (i = 1; i <= N; i++) {
		sum[i] = sum[i - 1] + A[i];
	}

	for (i = 0; i < Q; i++) {
		long long target = sum[R[i]] - sum[L[i] - 1];
		int no = L[i] - 1, yes = R[i];
		while (no + 1 < yes) {
			int m = no + (yes - no) / 2;
			long long meow = sum[m] - sum[L[i] - 1];
			if (meow * 2 > target) yes = m; else no = m;
		}
		printf("%d\n", yes);
	}

	return 0;
}

Submission Info

Judge Result