Submission #845025

#	Time	Username	Problem	Language	Result	Execution time	Memory
845025		Piokemon	Trampoline (info1cup20_trampoline)	C++17	57 / 100	651 ms	68936 KiB

trampoline

#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
• Subtask 2: 0 / 20
• Subtask 3: 11 / 11
• Subtask 4: 19 / 19
• Subtask 5: 27 / 27