oj.uz

Submission #426884

# Submission time Handle Problem Language Result Execution time Memory
426884 2021-06-14T10:41:02 Z jamezzz Trampoline (info1cup20_trampoline) C++17
0 / 100
 369 ms 20472 KB 
#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef pair<int,int> ii;

int r,c,n,t,a,b,xa,xb,ya,yb,nx[200005][20];
vector<ii> v,v1,v2;

int main(){
	sf("%d%d%d",&r,&c,&n);
	for(int i=0;i<n;++i){
		sf("%d%d",&a,&b);
		v.pb(a,b);
	}
	sort(all(v));
	for(int i=0;i<n;++i)nx[i][0]=-1;
	for(int i=0;i<n;++i){
		if(i!=0&&v[i].fi==v[i-1].fi+1){
			int cur=0;
			for(int j=0;j<sz(v2);++j){
				while(cur<sz(v1)&&v1[cur].fi<v2[j].fi)++cur;
				if(cur!=0)nx[v1[cur-1].se][0]=v2[j].se;
			}
			v1.clear();
			swap(v1,v2);
		}
		else if(i!=0&&v[i].fi!=v[i-1].fi){
			v1.clear();
			swap(v1,v2);
		}
		v2.pb(v[i].se,i);
	}
	int cur=0;
	for(int j=0;j<sz(v2);++j){
		while(cur<sz(v1)&&v1[cur].fi<v2[j].fi)++cur;
		if(cur!=0)nx[v1[cur-1].se][0]=v2[j].se;
	}
	/*
	for(int i=0;i<n;++i){
		pf("%d %d: %d\n",v[i].fi,v[i].se,nx[i][0]);
	}
	//*/
	for(int k=1;k<20;++k){
		for(int i=0;i<n;++i){
			if(nx[i][k-1]!=-1)nx[i][k]=nx[nx[i][k-1]][k-1];
			else nx[i][k]=-1;
		}
	}
	sf("%d",&t);
	for(int i=0;i<t;++i){
		sf("%d%d%d%d",&xa,&ya,&xb,&yb);
		if(xb<xa||yb<ya){
			pf("No\n");continue;
		}
		if(xa==xb){
			pf("Yes\n");continue;
		}
		int x=lower_bound(all(v),ii(xa,ya))-v.begin();
		if(x==sz(v)||v[x].fi!=xa){
			pf("No\n");continue;
		}
		int cur=x;
		for(int k=19;k>=0;--k){
			if(nx[cur][k]!=-1&&v[nx[cur][k]].fi<=xb)cur=nx[cur][k];
		}
		if(v[cur].fi<xb-1||v[cur].se>yb)pf("No\n");
		else pf("Yes\n");
	}
}

Compilation message

trampoline.cpp: In function 'int main()':
trampoline.cpp:17:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  sf("%d%d%d",&r,&c,&n);
      |    ^
trampoline.cpp:19:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |   sf("%d%d",&a,&b);
      |     ^
trampoline.cpp:56:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  sf("%d",&t);
      |    ^
trampoline.cpp:58:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   sf("%d%d%d%d",&xa,&ya,&xb,&yb);
      |     ^

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1100 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 118 ms 17684 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 Incorrect 272 ms 20472 KB expected YES, found NO [27th token]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 716 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 Incorrect 369 ms 18252 KB expected YES, found NO [1st token]
2 Halted 0 ms 0 KB -