Submission #1208437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208437		kaltspielerhy	Fountain (eJOI20_fountain)	C++20	100 / 100	332 ms	37516 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define VIDE nbFontaines+1
const int INFINI = 1e17;

struct fontaine {
    int taille, contenance;
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int nbFontaines, nbRequetes;
    cin >> nbFontaines >> nbRequetes;
    vector<fontaine> fontaines(nbFontaines);
    for (auto& it : fontaines) {
        cin >> it.taille >> it.contenance;
    }
    fontaines.push_back({INFINI, 0});

    // notations: les fontaines sont de 0 à nbFontaines-1 et nbFontaines la base
    vector<pair<int, int>> monotone;
    vector<int> parents(nbFontaines+1);
    monotone.push_back({0, fontaines[0].taille});
    for (int i = 1; i <= nbFontaines; i++) {
        while (!monotone.empty() && monotone.back().second < fontaines[i].taille) {
            parents[monotone.back().first] = i;
            monotone.pop_back();
        }
        monotone.push_back({i, fontaines[i].taille});
    }

    while (!monotone.empty()) {
        parents[monotone.back().first] = nbFontaines;
        monotone.pop_back();
    }

    // nbFontaines+1 est une place vide
    vector<vector<pair<int, int>>> ancetres(nbFontaines+2, vector<pair<int, int>>(18, {VIDE, 0}));
    for (int iNoeud = 0; iNoeud < nbFontaines; iNoeud++) {
        ancetres[iNoeud][0] = {parents[iNoeud], fontaines[iNoeud].contenance};
    }

    for (int iBit = 1; iBit < 18; iBit++) {
        for (int iNoeud = 0; iNoeud < nbFontaines; iNoeud++) {
            ancetres[iNoeud][iBit] = {ancetres[ancetres[iNoeud][iBit-1].first][iBit-1].first,
                                      ancetres[iNoeud][iBit-1].second + ancetres[ancetres[iNoeud][iBit-1].first][iBit-1].second};
        }
    }

    for (int iRequete = 0; iRequete < nbRequetes; iRequete++) {
        int depart, capacite;
        cin >> depart >> capacite;
        depart--;

        int bitD = 17;
        while (bitD >= 0) {
            while (bitD >= 0 && (ancetres[depart][bitD].first == VIDE || ancetres[depart][bitD].second >= capacite)) {
                bitD--;
            }
            if (bitD < 0) break;
            capacite -= ancetres[depart][bitD].second;
            depart = ancetres[depart][bitD].first;
            bitD--;
        }

        cout << (depart+1)%(nbFontaines+1) << '\n';
    }

    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40