제출 #1078118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1078118		horiaboeriu	Fountain (eJOI20_fountain)	C++17	100 / 100	108 ms	20308 KiB

fountain

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40