oj.uz

Submission #426971

# Submission time Handle Problem Language Result Execution time Memory
426971 2021-06-14T11:23:39 Z jamezzz Trampoline (info1cup20_trampoline) C++17
100 / 100
 539 ms 21064 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));int pv=-1;
	for(int i=0;i<n;++i)nx[i][0]=-1;
	for(int i=0;i<n;++i){
		v2.pb(v[i].se,i);
		if(i==n-1||v[i].fi!=v[i+1].fi){
			if(v[i].fi==pv+1){
				int cur=0;
				for(int j=0;j<sz(v2);++j){
					while(cur<sz(v1)&&v1[cur].fi<=v2[j].fi){
						++cur;
						nx[v1[cur-1].se][0]=v2[j].se;
					}
				}
			}
			v1.clear();
			swap(v1,v2);
			pv=v[i].fi;
		}
	}
	/*
	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-1)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:52:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  sf("%d",&t);
      |    ^
trampoline.cpp:54:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   sf("%d%d%d%d",&xa,&ya,&xb,&yb);
      |     ^

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1100 KB 200 token(s): yes count is 21, no count is 179
2 Correct 5 ms 1356 KB 200 token(s): yes count is 70, no count is 130
3 Correct 3 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 118 ms 17628 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 118 ms 17692 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 114 ms 17636 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 142 ms 17600 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 276 ms 20444 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 331 ms 19760 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 287 ms 18440 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 318 ms 18312 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 321 ms 18284 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 332 ms 18348 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 6 ms 716 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 7 ms 844 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 7 ms 824 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 6 ms 844 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 7 ms 908 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 7 ms 972 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 460 ms 18428 KB 200000 token(s): yes count is 171404, no count is 28596
2 Correct 419 ms 18612 KB 200000 token(s): yes count is 161254, no count is 38746
3 Correct 295 ms 18972 KB 200000 token(s): yes count is 117455, no count is 82545
4 Correct 432 ms 18560 KB 200000 token(s): yes count is 182118, no count is 17882
5 Correct 331 ms 20400 KB 200000 token(s): yes count is 167565, no count is 32435
6 Correct 328 ms 19996 KB 200000 token(s): yes count is 156797, no count is 43203
7 Correct 298 ms 19976 KB 200000 token(s): yes count is 156797, no count is 43203
8 Correct 277 ms 19136 KB 200000 token(s): yes count is 122100, no count is 77900
9 Correct 431 ms 18600 KB 200000 token(s): yes count is 139670, no count is 60330
10 Correct 406 ms 18556 KB 200000 token(s): yes count is 165806, no count is 34194
11 Correct 539 ms 18668 KB 200000 token(s): yes count is 175646, no count is 24354
12 Correct 284 ms 21064 KB 200000 token(s): yes count is 134695, no count is 65305
13 Correct 269 ms 20656 KB 200000 token(s): yes count is 126733, no count is 73267
14 Correct 343 ms 18608 KB 200000 token(s): yes count is 155290, no count is 44710
15 Correct 274 ms 20784 KB 200000 token(s): yes count is 129674, no count is 70326