oj.uz

Submission #1078118

# Submission time Handle Problem Language Result Execution time Memory
1078118 2024-08-27T12:55:01 Z horiaboeriu Fountain (eJOI20_fountain) C++17
100 / 100
 108 ms 20308 KB 
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAXL 18
#define MAXN 100000
#define INFINIT 2000000000
int poz[MAXL][MAXN + 1], sum[MAXL][MAXN + 1], lung[MAXN + 1], v[MAXN + 1], st[MAXN + 1];
int readInt() {
    int x;
    char ch;
    ch = fgetc(stdin);
    while (isspace(ch)) {
        ch = fgetc(stdin);
    }
    x = 0;
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = fgetc(stdin);
    }
    return x;
}
int main()
{
    int n, q, i, j, p, vf, p2, x, s;
    //tin cu un rmq al i-lea la care va ajunge dupa ce cade apa in jos de p ori(puetre a lui 2)
    //si tin si suma capacitatilor si fac cautarea binaar de la aib
    n = readInt();
    q = readInt();
    lung[0] = INFINIT;
    vf = 0;
    for (i = 1; i <= n; i++) {
        lung[i] = readInt();
        v[i] = readInt();
        while (lung[i] > lung[st[vf]]) {
            poz[0][st[vf]] = i;
            sum[0][st[vf]] = v[i];//suma capacitatilor a primelor (1 << j) pe care va cadea apa incepand de la st[vf]
            vf--;
        }
        vf++;
        st[vf] = i;
    }
    j = p = 1;
    while (p <= n) {
        for (i = 1; i <= n; i++) {
            poz[j][i] = poz[j - 1][poz[j - 1][i]];
            sum[j][i] = sum[j - 1][i] + sum[j - 1][poz[j - 1][i]];
        }
        j++;
        p *= 2;
    }
    p2 = 1;
    while ((1 << p2) <= n) {
        p2++;
    }
    p2--;
    for (i = 0; i < q; i++) {
        j = readInt();
        x = readInt();
        if (v[j] >= x) {
            printf("%d\n", j);
        } else {
            s = v[j];//pe asta nu am adunat-o in rmq
            for (p = p2; p >= 0; p--) {
                if (poz[p][j] > 0 && s + sum[p][j] < x) {
                    s += sum[p][j];
                    j = poz[p][j];
                }
            }
            //acum in j este ultimul la care apa inca e mai multa decat poate tine
            //deci in urmatorul apa se va opri
            printf("%d\n", poz[0][j]);
        }
    }
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 18208 KB Output is correct
2 Correct 78 ms 17284 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 66 ms 18208 KB Output is correct
9 Correct 78 ms 17284 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 37 ms 10588 KB Output is correct
12 Correct 108 ms 20308 KB Output is correct
13 Correct 87 ms 19972 KB Output is correct
14 Correct 57 ms 19284 KB Output is correct
15 Correct 42 ms 20052 KB Output is correct