oj.uz

Submission #642196

# Submission time Handle Problem Language Result Execution time Memory
642196 2022-09-18T20:37:12 Z oscar1f Fountain (eJOI20_fountain) C++17
100 / 100
 540 ms 39980 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,anci;
vector<int> aMettre;
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--) {
        if (anci>diam[i].first) {
            while (aMettre.size()>0) {
                proch.insert(aMettre.back());
                aMettre.pop_back();
            }
        }
        pos=diam[i].second;
        it=proch.lower_bound(pos);
        pere[pos][0][0]=(*it);
        aMettre.push_back(pos);
        anci=diam[i].first;
    }
    for (int i=0;i<LOG2;i++) {
        pere[nbRes+1][i][0]=nbRes+1;
        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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 656 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 33748 KB Output is correct
2 Correct 424 ms 31308 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 656 KB Output is correct
8 Correct 339 ms 33748 KB Output is correct
9 Correct 424 ms 31308 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 188 ms 21620 KB Output is correct
12 Correct 540 ms 39980 KB Output is correct
13 Correct 467 ms 39512 KB Output is correct
14 Correct 385 ms 38796 KB Output is correct
15 Correct 368 ms 39240 KB Output is correct