oj.uz

Submission #485906

# Submission time Handle Problem Language Result Execution time Memory
485906 2021-11-09T16:20:09 Z gavgav Fountain (eJOI20_fountain) C++17
100 / 100
 94 ms 8084 KB 
#include <iostream>
#define MAX_N 100000
#define MAX_M 200000
#define MAX_S 100000000000000
using namespace std;
struct reservoir {
    long long diameters, capacity;
};
struct query {
    int level, volume, rasp;
};
int main() {
    int next[MAX_M + 1], liste[MAX_N + 1];
    long long sumaNec[MAX_N + 1];
    fill(next, next + MAX_M + 1, 0);
    long long height, queries_number, top, i, j;
    long long sumaV;
    scanf( "%lld%lld", &height, &queries_number);
    long long stack[height + 1];
    struct reservoir reservoirs[height + 1];
    struct query queries[queries_number + 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:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf( "%lld%lld", &height, &queries_number);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:25:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         scanf( "%lld%lld", &reservoirs[i].diameters, &reservoirs[i].capacity);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf( "%d%d", &queries[i].level, &queries[i].volume);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2124 KB Output is correct
2 Correct 1 ms 2252 KB Output is correct
3 Correct 2 ms 2252 KB Output is correct
4 Correct 2 ms 2252 KB Output is correct
5 Correct 2 ms 2252 KB Output is correct
6 Correct 2 ms 2292 KB Output is correct
7 Correct 2 ms 2252 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 6552 KB Output is correct
2 Correct 69 ms 6732 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2124 KB Output is correct
2 Correct 1 ms 2252 KB Output is correct
3 Correct 2 ms 2252 KB Output is correct
4 Correct 2 ms 2252 KB Output is correct
5 Correct 2 ms 2252 KB Output is correct
6 Correct 2 ms 2292 KB Output is correct
7 Correct 2 ms 2252 KB Output is correct
8 Correct 64 ms 6552 KB Output is correct
9 Correct 69 ms 6732 KB Output is correct
10 Correct 2 ms 2252 KB Output is correct
11 Correct 39 ms 5120 KB Output is correct
12 Correct 94 ms 8068 KB Output is correct
13 Correct 82 ms 8084 KB Output is correct
14 Correct 69 ms 8004 KB Output is correct
15 Correct 77 ms 8072 KB Output is correct