Bear and Segments
Bear Limak has a sequence of N non-negative integers A1, A2,
.... AN. He defines the score of a segment (consecutive subsequence) as its sum of elements modulo P (not necessarily prime). Find the maximum score of a non-empty segment, and also find the number of segments with this maximum score.
Input
The first line of the input contains two space separated integers, N and P.
The second line contains N space separated integers denoting the sequence.
Output
Output two space separated integers denoting the maximum score of a segment and the number of segments with the score, respectively.
Constraints
• 1≤T≤10
• 1≤ N ≤105
• 1≤ P≤ 109
• 0 ≤ A≤ 109
Sample:
Input:
23
12
Output:
21
Explanation:
There are three segments - [1], [2] and [1, 2]. Sum of these segments are 1, 2 and 3 respectively. Sum of these segments modulo 3 will be 1, 2 and 0. Maximum score among these is 2. There is also only one segment with this
score.
Sample input
35
2 4 3
Sample output
4 2
Program:
#c
#include <stdio.h>
#include <stdlib.h>
int bisect_left(int *arr, int len, int v) {
int l = 0, r = len;
while (l < r) {
int mid = (l + r) >> 1;
if (arr[mid] < v) {
l = mid + 1;
}
else {
r = mid;
}
}
return l;
}
int bisect_right(int *arr, int len, int v) {
int l = 0, r = len;
while (l < r) {
int mid = (l + r) >> 1;
if (arr[mid] <= v) {
l = mid + 1;
}
else {
r = mid;
}
}
return l;
}
int main() {
int n, p;
scanf("%d %d", &n, &p);
int *data = malloc((n+1) * sizeof(int));
for (int i = 1; i <= n; i++) {
scanf("%d", &data[i]);
}
int *temp = malloc((n+1) * sizeof(int));
temp[0] = 0;
for (int i = 1; i <= n; i++) {
temp[i] = (temp[i-1] + data[i]) % p;
}
int record = 0;
int count = 0;
int *arr = malloc((n+1) * sizeof(int));
int len = 0;
for (int i = 0; i <= n; i++) {
int v = temp[i];
int j = bisect_right(arr, len, v);
int u, vv, delta;
if (j < len) {
u = arr[j];
vv = (v - u + p) % p;
} else {
u = 0;
vv = v;
}
delta = bisect_right(arr, len, u) - bisect_left(arr, len, u);
if (record < vv) {
record = vv;
count = delta;
} else if (record == vv) {
count += delta;
}
for (int k = len; k > j; k--) {
arr[k] = arr[k-1];
}
arr[j] = v;
len++;
}
printf("%d %d\n", record, count);
free(data);
free(temp);
free(arr);
return 0;
}
#Python
import bisect
def bisect_left(arr, v):
l, r = 0, len(arr)
while l < r:
mid = (l + r) // 2
if arr[mid] < v:
l = mid + 1
else:
r = mid
return l
def bisect_right(arr, v):
l, r = 0, len(arr)
while l < r:
mid = (l + r) // 2
if arr[mid] <= v:
l = mid + 1
else:
r = mid
return l
n, p = map(int, input().split())
data = list(map(int, input().split()))
temp = [0]
for v in data:
temp.append((temp[-1] + v) % p)
record = 0
count = 0
arr = []
for v in temp:
j = bisect_right(arr, v)
if j < len(arr):
u = arr[j]
vv = (v - u + p) % p
else:
u = 0
vv = v
delta = bisect_right(arr, u) - bisect_left(arr, u)
if record < vv:
record = vv
count = delta
elif record == vv:
count += delta
arr.insert(j, v)
print(record, count)
0 Comments