Submission #48926324

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll MOD=998244353;
// head 
const int N=2e5+5; 
vector<pair<int,int>> V;
int a[N],b[N],a1[N],b1[N];
bool cmp(pair<int,int> p,pair<int,int> q)
{
	if(p.second!=q.second) return p.second<q.second;
	return p.first<q.first;
}
signed main() 
{
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	
	int h,w;cin>>h>>w;
	int x,y;cin>>x>>y;
	int n;cin>>n;
	for(int i=0;i<n;i++){
		int X,Y;cin>>X>>Y;
		V.pb({X,Y});
	}	
	sort(all(V));
	for(int i=0;i<n;i++){
		a[i]=V[i].first;
		b[i]=V[i].second;
	}
	sort(all(V),cmp);
	for(int i=0;i<n;i++){
		a1[i]=V[i].first;
		b1[i]=V[i].second;
	}
	int q;cin>>q;
	while(q--)
	{
		char s;cin>>s;
		int step;cin>>step;
		if(s=='L'){
			int st=lower_bound(a,a+n,x)-a;
			int en=upper_bound(a,a+n,x)-a;
			int dir=lower_bound(b+st,b+en,y)-b-1;
			if(dir==st-1) y=max(1ll,y-step);
			else y=max(y-step,b[dir]+1);
		}
		else if(s=='R'){
			int st=lower_bound(a,a+n,x)-a;
			int en=upper_bound(a,a+n,x)-a;
			int dir=upper_bound(b+st,b+en,y)-b;
			if(dir==en) y=min(w,y+step);
			else y=min(y+step,b[dir]-1);
		}
		else if(s=='U'){
			int st=lower_bound(b1,b1+n,y)-b1;
			int en=upper_bound(b1,b1+n,y)-b1;
			int dir=lower_bound(a1+st,a1+en,x)-a1-1;
			if(dir==st-1) x=max(1ll,x-step);
			else x=max(x-step,a1[dir]+1);
		}
		else {
			int st=lower_bound(b1,b1+n,y)-b1;
			int en=upper_bound(b1,b1+n,y)-b1;
			int dir=upper_bound(a1+st,a1+en,x)-a1;
			if(dir==en) x=min(h,x+step);
			else x=min(x+step,a1[dir]-1);
		}
		cout<<x<<" "<<y<<endl;
	}
}

Submission Info

Judge Result