oj.uz

Submission #642195

# Submission time Handle Problem Language Result Execution time Memory
642195 2022-09-18T20:17:05 Z oscar1f Fountain (eJOI20_fountain) C++17
30 / 100
 386 ms 34000 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 34000 KB Output is correct
2 Correct 386 ms 31248 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -