oj.uz

Submission #346800

# Submission time Handle Problem Language Result Execution time Memory
346800 2021-01-11T05:34:02 Z arnold518 Trampoline (info1cup20_trampoline) C++14
100 / 100
 788 ms 55476 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int R, C, N, Q;
pii A[MAXN+10];
unordered_map<int, vector<pii>> M;
int par[MAXN+10][30];

int main()
{
	scanf("%d%d%d", &R, &C, &N);
	for(int i=1; i<=N; i++)
	{
		scanf("%d%d", &A[i].first, &A[i].second);
		M[A[i].first].push_back({A[i].second, i});
	}

	for(auto &it : M)
	{
		sort(it.second.begin(), it.second.end());
	}

	for(int i=1; i<=N; i++)
	{
		if(M.find(A[i].first+1)==M.end()) continue;
		auto it=lower_bound(M[A[i].first+1].begin(), M[A[i].first+1].end(), pii(A[i].second, 0));
		if(it==M[A[i].first+1].end()) par[i][0]=0;
		else par[i][0]=it->second;
		if(par[i][0]!=0) assert(A[par[i][0]].first==A[i].first+1);
	}

	A[0]={2e9, 2e9};
	for(int i=1; i<=20; i++) for(int j=1; j<=N; j++) par[j][i]=par[par[j][i-1]][i-1];

	scanf("%d", &Q);
	while(Q--)
	{
		int y1, x1, y2, x2;
		scanf("%d%d%d%d", &y1, &x1, &y2, &x2);
		if(x1>x2 || y1>y2)
		{
			printf("No\n");
			continue;
		}
		if(y1==y2 && x1<=x2)
		{
			printf("Yes\n");
			continue;
		}

		if(M.find(y1)==M.end())
		{
			printf("No\n");
			continue;
		}
		auto it=lower_bound(M[y1].begin(), M[y1].end(), pii(x1, 0));
		if(it==M[y1].end())
		{
			printf("No\n");
			continue;
		}
		int now=it->second;
		/*
		while(1)
		{
			if(A[par[now][0]].first>=y2) break;
			now=par[now][0];
		}
		*/

		for(int i=20; i>=0; i--)
		{
			if(A[par[now][i]].first<y2) now=par[now][i];
		}
		

		if(A[now].first!=y2-1)
		{
			printf("No\n");
			continue;
		}

		if(A[now].second<=x2)
		{
			printf("Yes\n");
		}
		else
		{
			printf("No\n");
		}
	}
}

Compilation message

trampoline.cpp: In function 'int main()':
trampoline.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |  scanf("%d%d%d", &R, &C, &N);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
trampoline.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |   scanf("%d%d", &A[i].first, &A[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
trampoline.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
trampoline.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |   scanf("%d%d%d%d", &y1, &x1, &y2, &x2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1516 KB 200 token(s): yes count is 21, no count is 179
2 Correct 5 ms 1772 KB 200 token(s): yes count is 70, no count is 130
3 Correct 4 ms 1388 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 170 ms 28584 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 176 ms 28396 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 165 ms 27628 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 167 ms 28524 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 381 ms 28512 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 416 ms 39888 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 426 ms 39916 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 429 ms 40556 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 461 ms 40684 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 589 ms 45200 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 7 ms 1004 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 7 ms 1388 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 8 ms 1772 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 7 ms 1388 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 8 ms 1388 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 7 ms 1388 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 741 ms 34448 KB 200000 token(s): yes count is 171404, no count is 28596
2 Correct 614 ms 42220 KB 200000 token(s): yes count is 161254, no count is 38746
3 Correct 408 ms 40048 KB 200000 token(s): yes count is 117455, no count is 82545
4 Correct 780 ms 55476 KB 200000 token(s): yes count is 182118, no count is 17882
5 Correct 561 ms 45468 KB 200000 token(s): yes count is 167565, no count is 32435
6 Correct 460 ms 40096 KB 200000 token(s): yes count is 156797, no count is 43203
7 Correct 437 ms 40180 KB 200000 token(s): yes count is 156797, no count is 43203
8 Correct 410 ms 39896 KB 200000 token(s): yes count is 122100, no count is 77900
9 Correct 693 ms 45328 KB 200000 token(s): yes count is 139670, no count is 60330
10 Correct 752 ms 45524 KB 200000 token(s): yes count is 165806, no count is 34194
11 Correct 788 ms 50356 KB 200000 token(s): yes count is 175646, no count is 24354
12 Correct 355 ms 39840 KB 200000 token(s): yes count is 134695, no count is 65305
13 Correct 376 ms 40032 KB 200000 token(s): yes count is 126733, no count is 73267
14 Correct 447 ms 40556 KB 200000 token(s): yes count is 155290, no count is 44710
15 Correct 387 ms 39548 KB 200000 token(s): yes count is 129674, no count is 70326