Submission #642195

#	Time	Username	Problem	Language	Result	Execution time	Memory
642195		oscar1f	Fountain (eJOI20_fountain)	C++17	30 / 100	386 ms	34000 KiB

fountain

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MAX_RES=100*1000+5,LOG2=18,INFINI=2*1000*1000*1000;
int nbRes,nbReq,taille,pos,rest;
vector<pair<int,int>> diam;
int pere[MAX_RES][LOG2][2];
set<int> proch;
set<int>::iterator it;

signed main() {
    ios_base::sync_with_stdio(false);
    cin>>nbRes>>nbReq;
    for (int i=1;i<=nbRes;i++) {
        cin>>taille>>pere[i][0][1];
        diam.push_back(make_pair(taille,i));
    }
    sort(diam.begin(),diam.end());
    proch.insert(nbRes+1);
    for (int i=nbRes-1;i>=0;i--) {
        pos=diam[i].second;
        it=proch.lower_bound(pos);
        pere[pos][0][0]=(*it);
        proch.insert(pos);
    }
    for (int i=0;i<LOG2;i++) {
        pere[nbRes+1][i][0]=nbRes;
        pere[nbRes+1][i][1]=INFINI;
    }
    for (int i=1;i<LOG2;i++) {
        for (int j=1;j<=nbRes;j++) {
            pere[j][i][0]=pere[pere[j][i-1][0]][i-1][0];
            pere[j][i][1]=pere[j][i-1][1]+pere[pere[j][i-1][0]][i-1][1];
        }
    }
    for (int i=0;i<nbReq;i++) {
        cin>>pos>>rest;
        for (int j=LOG2-1;j>=0;j--) {
            if (pere[pos][j][1]<rest) {
                rest-=pere[pos][j][1];
                pos=pere[pos][j][0];
                //cout<<j<<" : "<<pos<<" "<<rest<<endl;
            }
        }
        if (pos==nbRes+1) {
            pos=0;
        }
        cout<<pos<<endl;
    }
    return 0; 
}

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