Submission #447481

#	Time	Username	Problem	Language	Result	Execution time	Memory
447481		raid	Trampoline (info1cup20_trampoline)	C++17	100 / 100	1269 ms	28468 KiB

trampoline

#include <iostream>
#include <algorithm>
#include <map>
#define pii pair<int, int>
#define f first
#define s second

using namespace std;

const int MaxN = 200005;
const int MaxLg = 18;
const int INF = (int)1e9; 

pii gt[MaxN];
pii lim[MaxN]; 

int anc[MaxLg][MaxN];
int lg[MaxN];
map<int, int> conv;

struct cmp {
  bool operator () ( const pii &a, const pii &b ) {
	return (a.s < b.s) || (a.s == b.s && a.f < b.f);
  }
};

int main() {
  int l, c, n, ix = 0, t, xst, yst, xdr, ydr;

  cin >> l >> c >> n;
  for ( int i = 0; i < n; ++i ) {
	cin >> gt[i].s >> gt[i].f;
  }
  for ( int i = 2; i <= n; ++i ) {
	lg[i] = lg[i / 2] + 1;
  }
  gt[n].s = gt[n].f = INF + 1;
  sort( gt, gt + n, cmp() );
  lim[ix].f = 0;
  conv[gt[0].s] = ix;
  for ( int i = 1; i < n; ++i ) {
	if ( gt[i - 1].s != gt[i].s ) {
	  lim[ix++].s = i;
	  lim[ix].f = i;
	  conv[gt[i].s] = ix;
	}
  }
  lim[ix++].s = n;
  for ( int i = 0; i < n; ++i ) {
	int ix_now = conv[gt[i].s];
	if ( ix_now + 1 >= ix ) {
	  anc[0][i] = n;
	} else {
	  if ( gt[lim[ix_now + 1].f].s == gt[i].s + 1 ) {
		anc[0][i] = (lower_bound( gt + lim[ix_now + 1].f, gt + lim[ix_now + 1].s, gt[i] ) - gt);
	  } else {
        anc[0][i] = n;
	  }
	}
  }
  for ( int q = 1; q < MaxLg; ++q ) {
	for ( int i = 0; i < n; ++i ) {
	  anc[q][i] = anc[q - 1][anc[q - 1][i]];
	}
  }
  cin >> t; 
  while ( t-- ) {
	cin >> xst >> yst >> xdr >> ydr;
    if ( xdr - xst > n || xdr < xst || ydr < yst ) {
	  cout << "No\n";
	  continue;
	}
	if ( xst == xdr ) {
	  cout << "Yes\n";
	  continue;
	}
    int pos = lower_bound( gt + lim[conv[xst]].f, gt + lim[conv[xst]].s, make_pair( yst, xst ) ) - gt;
    int k = xdr - xst - 1;
	while ( k ) {
	  pos = anc[lg[k]][pos];
	  k -= (1 << lg[k]); 
	}
	if ( gt[pos].s == xdr - 1 && gt[pos].f <= ydr ) {
	  cout << "Yes\n";
	} else {
	  cout << "No\n";
	}
  }
  return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 11 / 11
• Subtask 4: 19 / 19
• Subtask 5: 27 / 27