Submission #439401

#	Time	Username	Problem	Language	Result	Execution time	Memory
439401		NintsiChkhaidze	Fountain (eJOI20_fountain)	C++14	100 / 100	999 ms	47208 KiB

fountain

#include <iostream>
#include <queue>
#define pb push_back
#define ll long long
#define int ll
using namespace std;
const int N = 100005;
int c[N],d[N],D[25][N],V[25][N],cntparent[N];
bool f[N];
deque <int> dq;
vector <int> v[N];

void dfs(int x){
  f[x] = 1;
  for (int w = 1; w <= 18; w++){
    D[w][x] = D[w - 1][D[w - 1][x]];
    V[w][x] = V[w - 1][D[w - 1][x]] + V[w - 1][x] - c[D[w - 1][x]];
  }

  for (int j=0;j<v[x].size();j++)
    dfs(v[x][j]);
}
int get(int x,int val){
  if (c[x] >= val) return x;
  if (!f[x]) return 0;
  
  int ans = -1;
  for (int j = 18; j >= 0; j--){
    if (D[j][x] == 0) continue;

    if (V[j][x] <= val) {
      val -= V[j][x];
      if (val == 0) {ans = D[j][x]; break;}
      x = D[0][D[j][x]];
      continue;
    }
    ans = D[j][x];
  }
  
  if (val && c[x] >= val) return x;
  if (ans == -1) return 0;
  return ans;
}
main() {
  int n,t;
  cin>>n>>t;

  for (int i = 1; i <= n; i++)
    cin>>d[i]>>c[i];
  
  dq.pb(n);
  for (int i = n - 1; i >= 1; i--){
    while (dq.size() && d[dq.back()] <= d[i])
      dq.pop_back();
    
    if (dq.size()){
      int idx = dq.back();
      D[0][i] = idx,V[0][i] = c[idx] + c[i];
      cntparent[i]++;
      v[idx].pb(i);
    } 

    dq.push_back(i);
  }
  
  for (int i = 1; i <= n; i++)
    if (!cntparent[i] && v[i].size()) dfs(i);
  
  while(t--){
    int ind,val;
    cin>>ind>>val;
    cout<<get(ind,val)<<"\n";
  }
}

Compilation message (stderr)

fountain.cpp: In function 'void dfs(long long int)':
fountain.cpp:20:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for (int j=0;j<v[x].size();j++)
      |                ~^~~~~~~~~~~~
fountain.cpp: At global scope:
fountain.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main() {
      | ^~~~

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