Submission #339691

#	Time	Username	Problem	Language	Result	Execution time	Memory
339691		wwdd	Trampoline (info1cup20_trampoline)	C++14	100 / 100	759 ms	69164 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
const int MN = 200200;
const int LOG = 20;
ll nx[MN][LOG];
struct Q {
	ll id;
	pl st,ed;
	bool operator< (const Q& other)  {
		return st.second < other.st.second;
	}
};
vector<Q> qu;
vector<pl> tr;
map<ll,ll> mu;
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll mr,mc;
	cin >> mr >> mc;
	ll n,N;
	cin >> n;
	for(int i=0;i<n;i++) {
		ll a,b;
		cin >> a >> b;
		tr.emplace_back(a,b);
	}
	sort(tr.begin(),tr.end(),[&](const pl& a, const pl& b){
			if(a.second > b.second) {return true;}
			if(a.second < b.second) {return false;}
			return a.first > b.first;
			});
	cin >> N;
	vector<ll> ans(N,0);
	for(int i=0;i<N;i++) {
		ll sr,sc,tr,tc;
		cin >> sr >> sc >> tr >> tc;
		qu.push_back({i,{sr,sc},{tr,tc}});
	}
	ll trp = 0;
	sort(qu.begin(),qu.end());
	for(int qi=N-1;qi>=0;qi--) {
		Q q = qu[qi];
		while(trp < tr.size() && tr[trp].second >= q.st.second) {
			ll r = tr[trp].first;
			mu[r] = trp;
			if(mu.count(r+1)) {
				nx[trp][0] = mu[r+1];
			} else {
				nx[trp][0] = trp;
			}
			for(int i=1;i<LOG;i++) {
				nx[trp][i] = nx[nx[trp][i-1]][i-1];
			}
			trp++;
		}
		ll idx = q.id;
		if(q.st.first == q.ed.first) {
			if(q.st.second <= q.ed.second)  {
				ans[idx] = 1;
			} else {
				ans[idx] = 0;
			}
		} else if(!mu.count(q.st.first)) {
				ans[idx] = 0;
		} else {
			ll no = mu[q.st.first];
			ll dif = q.ed.first-q.st.first-1;
			if(dif < 0) {ans[idx] = 0;} else {
				for(int i=LOG-1;i>=0;i--) {
					if(dif&(1<<i)) {
						no = nx[no][i];
					}
				}
			}
			if(tr[no].first+1 == q.ed.first && tr[no].second <= q.ed.second) {
				ans[idx] = 1;
			} else {
				ans[idx] = 0;
			}
		}
	}
	for(int i=0;i<N;i++) {
		cout << (ans[i]?"Yes":"No") << '\n';
	}
}

Compilation message (stderr)

trampoline.cpp: In function 'int main()':
trampoline.cpp:45:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   while(trp < tr.size() && tr[trp].second >= q.st.second) {
      |         ~~~~^~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 11 / 11
• Subtask 4: 19 / 19
• Subtask 5: 27 / 27