oj.uz

Submission #642194

# Submission time Handle Problem Language Result Execution time Memory
642194 2022-09-18T20:05:11 Z oscar1f Fountain (eJOI20_fountain) C++17
30 / 100
 433 ms 36796 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=0;i<nbRes;i++) {
        cin>>taille>>pere[i][0][1];
        diam.push_back(make_pair(taille,i));
    }
    sort(diam.begin(),diam.end());
    proch.insert(nbRes);
    for (int i=nbRes-1;i>=0;i--) {
        it=proch.lower_bound(diam[i].second);
        pere[diam[i].second][0][0]=(*it);
        proch.insert(diam[i].second);
    }
    for (int i=0;i<LOG2;i++) {
        pere[nbRes][i][0]=nbRes;
        pere[nbRes][i][1]=INFINI;
    }
    for (int i=1;i<LOG2;i++) {
        for (int j=0;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;
        pos--;
        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) {
            pos=-1;
        }
        cout<<pos+1<<endl;
    }
    return 0; 
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 2 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 391 ms 36796 KB Output is correct
2 Correct 433 ms 34280 KB Output is correct

Subtask #3
0 / 40.0

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