oj.uz

Submission #447481

# Submission time Handle Problem Language Result Execution time Memory
447481 2021-07-26T13:57:27 Z raid Trampoline (info1cup20_trampoline) C++17
100 / 100
 1269 ms 28468 KB 
#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.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1100 KB 200 token(s): yes count is 21, no count is 179
2 Correct 8 ms 1128 KB 200 token(s): yes count is 70, no count is 130
3 Correct 8 ms 972 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 16800 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 168 ms 16948 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 154 ms 16848 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 165 ms 16804 KB 4000 token(s): yes count is 1991, no count is 2009

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 944 ms 17408 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 931 ms 17348 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 939 ms 17424 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 961 ms 17644 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 940 ms 17692 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 1010 ms 21144 KB 200000 token(s): yes count is 97163, no count is 102837

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 844 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 24 ms 844 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 25 ms 1120 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 25 ms 828 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 24 ms 920 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 24 ms 832 KB 5000 token(s): yes count is 3390, no count is 1610

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1144 ms 21888 KB 200000 token(s): yes count is 171404, no count is 28596
2 Correct 1073 ms 18556 KB 200000 token(s): yes count is 161254, no count is 38746
3 Correct 938 ms 17476 KB 200000 token(s): yes count is 117455, no count is 82545
4 Correct 1269 ms 28468 KB 200000 token(s): yes count is 182118, no count is 17882
5 Correct 1071 ms 21632 KB 200000 token(s): yes count is 167565, no count is 32435
6 Correct 968 ms 17392 KB 200000 token(s): yes count is 156797, no count is 43203
7 Correct 957 ms 17476 KB 200000 token(s): yes count is 156797, no count is 43203
8 Correct 977 ms 17368 KB 200000 token(s): yes count is 122100, no count is 77900
9 Correct 1107 ms 21284 KB 200000 token(s): yes count is 139670, no count is 60330
10 Correct 1129 ms 21232 KB 200000 token(s): yes count is 165806, no count is 34194
11 Correct 1194 ms 24796 KB 200000 token(s): yes count is 175646, no count is 24354
12 Correct 933 ms 17400 KB 200000 token(s): yes count is 134695, no count is 65305
13 Correct 918 ms 17368 KB 200000 token(s): yes count is 126733, no count is 73267
14 Correct 1000 ms 17496 KB 200000 token(s): yes count is 155290, no count is 44710
15 Correct 952 ms 17424 KB 200000 token(s): yes count is 129674, no count is 70326