oj.uz

Submission #346790

# Submission time Handle Problem Language Result Execution time Memory
346790 2021-01-11T05:11:21 Z arnold518 Trampoline (info1cup20_trampoline) C++14
0 / 100
 458 ms 75116 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];
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++)
	{
		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;
	}

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

	scanf("%d", &Q);
	while(Q--)
	{
		int y1, x1, y2, x2;
		scanf("%d%d%d%d", &y1, &x1, &y2, &x2);
		if(y1==y2 && x1<=x2)
		{
			printf("Yes\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;
		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:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
trampoline.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |   scanf("%d%d%d%d", &y1, &x1, &y2, &x2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1644 KB expected YES, found NO [1st token]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 30376 KB expected YES, found NO [3rd token]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 176 ms 59760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1388 KB expected YES, found NO [1st token]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 458 ms 75116 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -