Submission #440191

#	Time	Username	Problem	Language	Result	Execution time	Memory
440191		raid	Fountain (eJOI20_fountain)	C++17	60 / 100	1560 ms	27768 KiB

fountain

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100005;
const int MAXLOG = 18;

struct rsv {
  int diam, vol;
} v[MAXN];

vector<int> s; 
vector<int> G[MAXN];
int S[MAXN];

int anc[MAXN][MAXLOG];
int lg2[MAXN], lev[MAXN], w[MAXN];

int getAnc( int node, int k ) {
  int lg = lg2[k];
  while ( k ) {
	node = anc[node][lg];
	k -= (1 << lg);
	lg = lg2[k];
  }
  return node;
}
void DFS( int node, int dep ) {
  w[node] = 1;
  lev[node] = dep;
  for ( int i = 0; i < (int)G[node].size(); ++i ) {
	if ( !w[G[node][i]] ) {
	  S[G[node][i]] = S[node] + v[G[node][i]].vol;
	  DFS( G[node][i], dep + 1 );
	}
  }
}
int bsn( int node, int sum ) {
  int l = 0, r = lev[node], mid, mid_node;
  
  if ( v[node].vol >= sum ) {
	return node;
  }
  while ( r - l > 1 ) {
    mid = (l + r) / 2;
	mid_node = getAnc( node, lev[node] - mid + 1 );
	if ( S[node] - S[mid_node] < sum ) {
	  r = mid;
	} else {
	  l = mid;
	}
  }
  return getAnc( node, lev[node] - l );
}

int main() {
  int n, q, fvol, k;

  cin >> n >> q;
  for ( int i = 1; i <= n; ++i ) {
	cin >> v[i].diam >> v[i].vol;
  }
  s.push_back( 1 );
  for ( int i = 2; i <= n; ++i ) {
	while ( s.size() && v[s.back()].diam < v[i].diam ) {
	  G[i].push_back( s.back() );
	  anc[s.back()][0] = i;
	  s.pop_back();
	}
	s.push_back( i );
  }
  while ( s.size() ) {
	G[0].push_back( s.back() );
	anc[s.back()][0] = 0;
	s.pop_back();
  }
  DFS( 0, 0 );
  for ( int p = 1; p <= MAXLOG - 1; ++p ) {
    for	( int i = 1; i <= n; ++i ) {
      anc[i][p] = anc[anc[i][p - 1]][p - 1];
	}
  }
  for ( int i = 2; i <= n; ++i ) {
	lg2[i] = lg2[i >> 1] + 1;
  }
  while ( q-- ) {
    cin >> k >> fvol;
    cout << bsn( k, fvol ) << "\n";
  }
  return 0;
}
/*
  int b = getAnc( node, lev[node] - r );
  
  if ( S[node] - S[a] <= sum && S[node] - S[b] <= sum ) {
	if ( l < r ) {
	  return a;
	}
	return b;
  } else if ( S[node] - S[a] <= sum ) {
	return a;
  }
*/

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