oj.uz

Submission #845034

# Submission time Handle Problem Language Result Execution time Memory
845034 2023-09-06T11:29:42 Z Piokemon Trampoline (info1cup20_trampoline) C++17
0 / 100
 230 ms 57240 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
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 30296 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 108 ms 43088 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 81 ms 41632 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 23 ms 30312 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 230 ms 57240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -