oj.uz

Submission #1039337

# Submission time Handle Problem Language Result Execution time Memory
1039337 2024-07-30T18:30:14 Z Shadxwed Fountain (eJOI20_fountain) C++
0 / 100
 1500 ms 4664 KB 
#include <cstdio>
#include <cstdlib>

typedef struct {
    int volume;
    int parent;
    int i;
} treeStruct;

typedef struct {
    int size;
    int i;
} stackStruct;

int main() {
    int n, q;
    scanf("%d %d", &n, &q);
    int *v = (int*)calloc(n, sizeof(int));
    int *d = (int*)calloc(n, sizeof(int));
    for(int i = 0; i < n; i++) {
        scanf("%d %d", d+i, v+i);
    }
    stackStruct *stk = (stackStruct*)calloc(n+1, sizeof(stackStruct));
    int lenStk = 1;
    treeStruct *tree = (treeStruct*)calloc(n+1, sizeof(treeStruct));
    stk[0] = (stackStruct){1000000001, 0};
    tree[0] = (treeStruct){0, 0, 0};
    for(int i = n-1; i >= 0; i--) {
        int curr = d[i];
        if(curr < stk[lenStk - 1].size) {
            stk[lenStk++] = (stackStruct){curr, i+1};
        } else {
            while(stk[(--lenStk)-1].size < curr);
            stk[lenStk++] = (stackStruct){curr, i+1};
        }
        tree[i+1].parent = stk[lenStk-2].i;
        tree[i+1].volume = tree[tree[i+1].parent].volume + v[i];
        tree[i+1].i = i+1;
    }
    int r, vol;
    for(int p = 0; p < q; p++) {
        scanf("%d %d", &r, &vol);
        treeStruct node = tree[r];
        if(node.volume < vol) {
            printf("0\n");
            continue;
        }
        while(true) {
            treeStruct parent = tree[node.parent];
            vol -= v[node.i-1];
            if(vol <= 0) {
                printf("%d\n", node.i);
                break;
            }
            node = parent;
        }
    }
    free(v);
    free(d);
    free(stk);
    free(tree);
}

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("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
fountain.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d %d", d+i, v+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
fountain.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%d %d", &r, &vol);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1585 ms 4664 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Incorrect 1 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -