oj.uz

Submission #409131

# Submission time Handle Problem Language Result Execution time Memory
409131 2021-05-20T08:50:54 Z victoriad Fountain (eJOI20_fountain) C++14
100 / 100
 420 ms 31736 KB 
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <iomanip>
#include <stack>
#include <fstream>
using namespace std;
 vector<int>v;
 vector<int>d;
vector<vector<int> >up;
int search(int l,vector<int>&ps,int r){
    int low=0,hi=18,mid,re=-1;
    while(low<=hi){
        mid=low+(hi-low)/2;
        if(ps[up[r][mid]]>l){
            low=mid+1;
            re=mid;
        }
        else{
            hi=mid-1;
        }
    }
    if(re==-1)return 0;
    if(ps[up[r][1]]<=l)return up[r][re]+1;
    return search(l,ps,up[r][re]);
}
 void suma(vector<int>&ps,vector<vector<int> >&c,int nodo){
     if(up[nodo][1]==-1)ps[nodo]=v[nodo];
     else ps[nodo]=ps[up[nodo][1]]+v[nodo];
     for(int y:c[nodo]){
             suma(ps,c,y);
     }
 }
 
int main(){
  ios::sync_with_stdio(false);
   cin.tie(NULL);
    int n,q;
    cin>>n>>q;
    int l,r;
    v.resize(n);
    d.resize(n);
    for(int i=0;i<n;i++){
      cin>>d[i]>>v[i];
    }
    vector<vector<int> >con(n);
    up.resize(n);
    vector<int>a(28,-1);
    for(int i=0;i<n;i++)up[i]=a;
    for(int i=0;i<n;i++)up[i][0]=i;
    int an=-1,u=0;
    up[n-1][1]=-1;
    int x=d[n-1];
    priority_queue<pair<int,int> >pq;
    pq.push(make_pair(1e9-d[0],0));
    for(int i=1;i<n-1;i++){
        while(!pq.empty()){
            int p=pq.top().first;
            int k=pq.top().second;
            if(p>1e9-d[i]){
                up[k][1]=i;
                con[i].push_back(k);
                pq.pop();
            }
            else{
                break;
            }
        }
        pq.push(make_pair(1e9-d[i],i));
 
    }
    vector<int>ps(n,0);
    for (int i=0;i<n;i++){
        if(up[i][1]==-1){
            suma(ps,con,i);
        }
    }
 
    for(int l=2;l<18;l++){
        for(int i=0;i<n;i++){
            if(up[i][l-1]!=-1)up[i][l]=up[up[i][l-1]][l-1];
        }
    }
 
    for(int i=0;i<q;i++){
        cin>>r>>l;
        r--;
        if(l<=v[r])cout<<r+1<<"\n";
        else if(ps[r]-l<0)cout<<0<<"\n";
        else cout<<search(ps[r]-l,ps,r)<<"\n";
    }
    
    
  return 0;
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:56:9: warning: unused variable 'an' [-Wunused-variable]
   56 |     int an=-1,u=0;
      |         ^~
fountain.cpp:56:15: warning: unused variable 'u' [-Wunused-variable]
   56 |     int an=-1,u=0;
      |               ^
fountain.cpp:58:9: warning: unused variable 'x' [-Wunused-variable]
   58 |     int x=d[n-1];
      |         ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 27440 KB Output is correct
2 Correct 333 ms 27244 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 280 ms 27440 KB Output is correct
9 Correct 333 ms 27244 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 116 ms 14376 KB Output is correct
12 Correct 420 ms 31736 KB Output is correct
13 Correct 274 ms 26436 KB Output is correct
14 Correct 187 ms 24712 KB Output is correct
15 Correct 160 ms 24504 KB Output is correct