oj.uz

Submission #845038

# Submission time Handle Problem Language Result Execution time Memory
845038 2023-09-06T11:30:44 Z Piokemon Trampoline (info1cup20_trampoline) C++17
100 / 100
 703 ms 63952 KB 
#include <bits/stdc++.h>
using namespace std;

constexpr int N = 2e5;
constexpr int K = 19;
int jmp[N+9][K+9];
vector<pair<int,int>> poz[2*N+9];
map<int,int> nowe;
int stare[2*N+9];
int miejsce[2*N+9];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int r,c,n,t,x1,y1,x2,y2,nr=1;
	cin >> r >> c >> n;
	for (int x=1;x<=n;x++){
		cin >> x1 >> y1;
		miejsce[x] = y1;
		if (nowe[x1] == 0){
			stare[nr] = x1;
			nowe[x1] = nr++;
			poz[nr-1].push_back({1e9+9,0});
		}
		poz[nowe[x1]].push_back({y1,x});
		if (nowe[x1+1] == 0){
			stare[nr] = x1+1;
			nowe[x1+1] = nr++;
			poz[nr-1].push_back({1e9+9,0});
		}
		poz[nowe[x1+1]].push_back({y1,-x});
	}
	miejsce[0] = 1e9+9;
	for (int x=1;x<nr;x++) sort(poz[x].begin(),poz[x].end());
	vector<int> czeka;
	for (int x=1;x<nr;x++){
		czeka.clear();
		for (pair<int,int> y:poz[x]){
			if (y.second > 0){
				for (int z:czeka) jmp[z][0] = y.second;
				czeka.clear();
			}
			else{
				czeka.push_back(-y.second);
			}
		}
	}
	for (int k=1;k<K;k++){
		for (int x=1;x<=n;x++){
			jmp[x][k] = jmp[jmp[x][k-1]][k-1];
		}
	}
	cin >> t;
	while(t--){
		cin >> x1 >> y1 >> x2 >> y2;
		if (x2<x1 || y2<y1){
			cout << "No\n";
			continue;
		}
		if (x1==x2){
			cout << "Yes\n";
			continue;
		}
		if (nowe[x1] == 0){
			cout << "No\n";
			continue;
		}
		int temp = nowe[x1];
		int v,zost;
		int pocz,kon,srod;
		pocz = 0;
		kon = poz[temp].size()-1;
		while(pocz<kon){
			srod = (pocz+kon)/2;
			if (poz[temp][srod].first < y1) pocz = srod+1;
			else kon = srod;
		}
		if (poz[temp][pocz].second>0){
			zost = x2-x1-1;
			v = poz[temp][pocz].second;
		}
		else{
			zost = x2-x1;
			v = -poz[temp][pocz].second;
		}
		//cout << v << ' ' << zost << '\n';
		for (int k=0;k<K;k++){
			if (zost & (1<<k)) v = jmp[v][k];
		}
		if (miejsce[v] <= y2) cout << "Yes\n";
		else cout << "No\n";
	}
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14936 KB 200 token(s): yes count is 21, no count is 179
2 Correct 6 ms 15196 KB 200 token(s): yes count is 70, no count is 130
3 Correct 6 ms 14936 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 127 ms 40552 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 119 ms 42320 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 100 ms 40876 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 127 ms 42504 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 188 ms 41288 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 203 ms 45400 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 192 ms 45388 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 256 ms 46676 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 249 ms 46672 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 392 ms 51880 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 14936 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 7 ms 15264 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 10 ms 15704 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 6 ms 15192 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 9 ms 15388 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 7 ms 15196 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 470 ms 49060 KB 200000 token(s): yes count is 171404, no count is 28596
2 Correct 339 ms 48724 KB 200000 token(s): yes count is 161254, no count is 38746
3 Correct 208 ms 45952 KB 200000 token(s): yes count is 117455, no count is 82545
4 Correct 703 ms 63952 KB 200000 token(s): yes count is 182118, no count is 17882
5 Correct 370 ms 52208 KB 200000 token(s): yes count is 167565, no count is 32435
6 Correct 257 ms 45372 KB 200000 token(s): yes count is 156797, no count is 43203
7 Correct 235 ms 45504 KB 200000 token(s): yes count is 156797, no count is 43203
8 Correct 206 ms 45544 KB 200000 token(s): yes count is 122100, no count is 77900
9 Correct 438 ms 52084 KB 200000 token(s): yes count is 139670, no count is 60330
10 Correct 460 ms 52256 KB 200000 token(s): yes count is 165806, no count is 34194
11 Correct 619 ms 57296 KB 200000 token(s): yes count is 175646, no count is 24354
12 Correct 184 ms 46128 KB 200000 token(s): yes count is 134695, no count is 65305
13 Correct 184 ms 45392 KB 200000 token(s): yes count is 126733, no count is 73267
14 Correct 261 ms 46824 KB 200000 token(s): yes count is 155290, no count is 44710
15 Correct 187 ms 45356 KB 200000 token(s): yes count is 129674, no count is 70326