# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1023385 | Shadxwed | Fountain (eJOI20_fountain) | C11 | 1532 ms | 2200 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <stdlib.h>
// Function to compare two integers (for qsort)
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int main() {
int n, q;
// Reading number of elements and queries
scanf("%d %d", &n, &q);
int *d = malloc(n * sizeof(int));
int *v = malloc(n * sizeof(int));
int *prefixSum = malloc((n + 1) * sizeof(int));
int *indices = malloc(n * sizeof(int));
// Reading values into arrays
for (int i = 0; i < n; i++) {
scanf("%d %d", &d[i], &v[i]);
indices[i] = i; // Initialize indices
}
// Compute prefix sums
prefixSum[0] = 0;
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i - 1] + v[i - 1];
}
// Sort indices based on the values in d
qsort(indices, n, sizeof(int), compare);
int q1, q2;
for (int i = 0; i < q; i++) {
scanf("%d %d", &q1, &q2);
q1--;
int prev = -1;
int remaining = q2;
// Binary search to find the appropriate segment
for (int j = q1; j < n; j++) {
int idx = indices[j];
if (d[idx] > prev) {
remaining -= v[idx];
prev = d[idx];
if (remaining <= 0) {
printf("%d\n", idx + 1);
break;
}
}
}
if (remaining > 0) {
printf("0\n");
}
}
// Free allocated memory
free(d);
free(v);
free(prefixSum);
free(indices);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |