oj.uz

답안 #485907

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
485907 2021-11-09T16:20:54 Z gavgav Fountain (eJOI20_fountain) C++17
100 / 100
 102 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2124 KB Output is correct
2 Correct 1 ms 2252 KB Output is correct
3 Correct 1 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 2252 KB Output is correct
7 Correct 2 ms 2252 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 6548 KB Output is correct
2 Correct 80 ms 6728 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2124 KB Output is correct
2 Correct 1 ms 2252 KB Output is correct
3 Correct 1 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 2252 KB Output is correct
7 Correct 2 ms 2252 KB Output is correct
8 Correct 68 ms 6548 KB Output is correct
9 Correct 80 ms 6728 KB Output is correct
10 Correct 2 ms 2252 KB Output is correct
11 Correct 40 ms 5120 KB Output is correct
12 Correct 102 ms 8004 KB Output is correct
13 Correct 91 ms 8072 KB Output is correct
14 Correct 70 ms 8084 KB Output is correct
15 Correct 85 ms 8004 KB Output is correct