Submission #222224

#	Time	Username	Problem	Language	Result	Execution time	Memory
222224		ryansee	Trampoline (info1cup20_trampoline)	C++14	0 / 100	2089 ms	42668 KiB

trampoline

#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (200006)
ll r,c,n,q,num[MAXN],order[MAXN];
pi A[MAXN];
dpi qu[MAXN];
vector<pi>Q,rows[MAXN];
vector<ll> d,dc,cols[MAXN];
bitset<MAXN>ans;
vector<deque<ll>> dq;
int main(){
	FAST
	cin>>r>>c>>n;
	FOR(i,1,n){
		cin>>A[i].f>>A[i].s;
		d.eb(A[i].f);
		dc.eb(A[i].s);
	}
	sort(all(d)), d.resize(unique(all(d))-d.begin());
	sort(all(dc)), dc.resize(unique(all(dc))-dc.begin());
	FOR(i,1,n){
		cols[lbd(dc,A[i].s)].pb(i);
		rows[lbd(d,A[i].f)].eb(A[i].s,i);
	}
	FOR(i,0,siz(dc)-1) sort(all(cols[i]),[](int x,int y){return A[x].f>A[y].f;});
	FOR(i,0,siz(d)-1) sort(all(rows[i]));
	cin>>q;
	FOR(i,1,q){
		ll a,b,x,y;cin>>a>>b>>x>>y;
		qu[i]=dpi(pi(a,b),pi(x,y));
		auto exist=[&](ll a,ll b){
			ll p1=lbd(d,a),p2=lbd(d,b);
			if(p1==siz(d)||d[p1]!=a||p2==siz(d)||d[p2]!=b)return 0;
			return int(p2-p1==b-a);
		};
		if(a>x||(a!=x&&!exist(a,x-1))||b>y) ans[i]=0;
		else if(a==x) ans[i]=1;
		else{
			Q.eb(b,-i), Q.eb(y,i);
		}
	}
	mmst(num,-1);
	sort(all(Q),greater<pi>());
	ll pre=siz(dc);
	for(auto i:Q){
		i.f=lbd(dc,i.f);
		while(pre>i.f){
			--pre;
			for(auto ind:cols[pre]){
				ll r=lbd(d,A[ind].f);
				if(r==siz(d)-1||d[r+1]!=A[ind].f+1||rows[r+1].back().f<A[ind].s){//start new
					num[ind]=siz(dq);order[ind]=0;
					dq.pb(deque<ll>()={A[ind].s});
				}else{
					ll guy=rows[r+1][lbd(rows[r+1],pi(A[ind].s,0))].s;
					num[ind]=num[guy];assert(~num[ind]);order[ind]=dq[num[ind]].size();
					dq[num[ind]].push_front(A[ind].s);
					FOR(i,1,siz(dq[num[ind]])-1)assert(dq[num[ind]][i]>=dq[num[ind]][i-1]);
				}
			}
		}
		if(i.s<0){
			i.s*=-1;
			ll a=qu[i.s].f.f,b=qu[i.s].f.s,x=qu[i.s].s.f,y=qu[i.s].s.s;
			-- x;
			ll guy1=lbd(rows[lbd(d,a)],pi(b,0));
			if(guy1==rows[lbd(d,a)].size()) continue;
			guy1=rows[lbd(d,a)][guy1].s; assert(~num[guy1]);
			ll pos=siz(dq[num[guy1]])-1-order[guy1];
			if(siz(dq[num[guy1]])-pos<x-a+1)continue;
			if(dq[num[guy1]][pos+x-a]>y)continue;
			ans[i.s]=1;
		}
	}
	FOR(i,1,q)cout<<(ans[i]?"Yes":"No")<<'\n';
}

Compilation message (stderr)

trampoline.cpp: In function 'int main()':
trampoline.cpp:92:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(guy1==rows[lbd(d,a)].size()) continue;
       ~~~~^~~~~~~~~~~~~~~~~~~~~~~

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