Submission #440327

#	Time	Username	Problem	Language	Result	Execution time	Memory
440327		raid	Fountain (eJOI20_fountain)	C++17	100 / 100	971 ms	28244 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[MAXLOG][MAXN];
int lg2[MAXN], lev[MAXN], w[MAXN];

inline int getAnc( int node, int k ) {
  int lg = lg2[k];
  while ( k ) {
	node = anc[lg][node];
	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 );
	}
  }
}
inline int fth( int node ) {
  return anc[0][node];
}
inline int bsn( int node, int sum ) {
  int k = lev[node], s = 0, lg = lg2[k], mid_node;
  int cpnode = node;

  if ( v[node].vol >= sum ) {
	return node;
  }

  while ( k && s + S[node] - S[anc[lg][node]] < sum ) {
	s += (S[node] - S[anc[lg][node]]);
	node = anc[lg][node];
	k -= (1 << lg);
	lg = lg2[k];
  }
  while ( lg ) {
	mid_node = anc[--lg][node];
	if ( s + S[node] - S[mid_node] < sum ) {
      s += S[node] - S[mid_node];
	  node = mid_node;
	}
  }
  return node;
}

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[0][s.back()] = i;
	  s.pop_back();
	}
	s.push_back( i );
  }
  while ( s.size() ) {
	G[0].push_back( s.back() );
	anc[0][s.back()] = 0;
	s.pop_back();
  }
  DFS( 0, 0 );
  for ( int p = 1; p < MAXLOG; ++p ) {
    for	( int i = 1; i <= n; ++i ) {
      anc[p][i] = anc[p - 1][anc[p - 1][i]];
	}
  }
  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;
}

Compilation message (stderr)

fountain.cpp: In function 'int bsn(int, int)':
fountain.cpp:44:7: warning: unused variable 'cpnode' [-Wunused-variable]
   44 |   int cpnode = node;
      |       ^~~~~~

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