Submission #1207662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207662		dssfsuper2	Fountain (eJOI20_fountain)	C++20	100 / 100	486 ms	19188 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define all(x) (x).begin(), (x).end()
const int INF = 1e9+7;
vector<int> par;
//first anc at which total>=v
int main(){
  int n, q;cin>>n>>q;
  vector<pii> reser(n+1);
  for(int i = n;i>=1;i--){
    cin>>reser[i].first>>reser[i].second;
  }
  reser[0]={INF, INF};
  vector<int> par(n+1, 0);
  vector<pii> mono={{INF, 0}};
  for(int i = 1;i<=n;i++){
    while (mono.back().first<=reser[i].first)mono.pop_back();
    par[i]=mono.back().second;
    mono.push_back({reser[i].first, i});
  }
  //jump: eats node and sum, when at node not yet counted, so I need last node with total<v
  vector<vector<pii>> jump(20, vector<pii>(n+1));
  for(int i = 0;i<20;i++){
    jump[i][0]={INF, 0};
    for(int j = 1;j<=n;j++){
      if (i==0)jump[i][j]={reser[j].second, par[j]};
      else jump[i][j]={min(INF, jump[i-1][j].first+jump[i-1][jump[i-1][j].second].first), jump[i-1][jump[i-1][j].second].second};
    }
  }
  for(int i = 0;i<q;i++){
    int r, v;cin>>r>>v;
    r=n-r+1;
    for(int j = 19;j>=0;j--){
      if (jump[j][r].first<v){
        v-=jump[j][r].first;
        r=jump[j][r].second;
        //cout << v << ' ' << r << '\n';
      }
    }
    r=(r==0 ? 0:n-r+1);
    cout << r << '\n';
  }
}

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