oj.uz

Submission #485901

# Submission time Handle Problem Language Result Execution time Memory
485901 2021-11-09T16:11:27 Z gavgav Fountain (eJOI20_fountain) C++17
100 / 100
 102 ms 7360 KB 
#include <stdio.h>
#define MAX_N 100000
#define MAX_M 200000
#define MAX_S 100000000000000
struct reservoir {
    long long diameters, capacity;
};
struct query {
    int level, volume, rasp;
};
int stack[MAX_N + 1], next[MAX_M + 1], liste[MAX_N + 1];
long long sumaNec[MAX_N + 1];
struct query queries[MAX_M + 1];
int main() {
    long long height, queries_number, top, i, j;
    long long sumaV;
    scanf( "%lld%lld", &height, &queries_number);
    struct reservoir reservoirs[height + 1];
    reservoirs[0].diameters = 1000000001;
    reservoirs[0].capacity = 0;
    for (i = 1; i <= height; ++i)
        scanf( "%lld%lld", &reservoirs[i].diameters, &reservoirs[i].capacity);
    for (i = 1; i <= queries_number; ++i) {
        scanf( "%d%d", &queries[i].level, &queries[i].volume);
        next[i] = liste[queries[i].level];
        liste[queries[i].level] = i;
    }
    stack[0] = 0;
    sumaNec[0] = -MAX_S - 1;
    top = 0;
    sumaV = 0;
    long long left, middle, right;
    for (i = height; i >= 1; --i) {
        while ( reservoirs[i].diameters >= reservoirs[stack[top]].diameters ) {
            sumaV -= reservoirs[stack[top]].capacity;
            --top;
        }
        ++top;
        stack[top] = i;
        sumaNec[top] = sumaV;
        sumaV += reservoirs[i].capacity;
        j = liste[i];
        while (j != 0) {
            right = top + 1;
            left = 0;
            while (right - left > 1 ) {
                middle = (right + left) / 2;
                if (sumaV - sumaNec[middle] >= queries[j].volume)
                    left = middle;
                else
                    right = middle;
            }
            queries[j].rasp = stack[left];
            j = next[j];
        }
    }
    for (i = 1; i <= queries_number; ++i)
        printf("%d\n", queries[i].rasp);
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf( "%lld%lld", &height, &queries_number);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf( "%lld%lld", &reservoirs[i].diameters, &reservoirs[i].capacity);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf( "%d%d", &queries[i].level, &queries[i].volume);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 5580 KB Output is correct
2 Correct 76 ms 5828 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 82 ms 5580 KB Output is correct
9 Correct 76 ms 5828 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 42 ms 3424 KB Output is correct
12 Correct 102 ms 7360 KB Output is correct
13 Correct 89 ms 6728 KB Output is correct
14 Correct 71 ms 6516 KB Output is correct
15 Correct 69 ms 6492 KB Output is correct