关于 ABC D
  • 板块学术版
  • 楼主QQ82272760
  • 当前回复11
  • 已保存回复11
  • 发布时间2022/10/15 21:54
  • 上次更新2023/10/27 07:21:29
查看原帖
关于 ABC D
189682
QQ82272760楼主2022/10/15 21:54

蒟蒻交了 77 发才卡过去。

不被卡常的大佬都是怎么写的啊?

#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int h,w,n,r,c,q;
int hh,ww;
vector<int>v1[200005],v2[200005];
vector<int>::iterator it;
int a[200005],b[200005];
struct wal{
	int x,y;
}p[200005];
bool cmpx(wal x,wal y){
	return x.x<y.x;
}
bool cmpy(wal x,wal y){
	return x.y<y.y;
}
inline void read(int &x){
	x=0; char ch=getchar();
	while(ch<'0'||'9'<ch) ch=getchar();
	while('0'<=ch&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return;
}
int main(){
	int l,lmt,x,y,rr,cc; char d[5];
	read(h); read(w); read(r); read(c); read(n);
	for(int i=1;i<=n;i+=1){
		read(x); read(y);
		p[i].x=a[i]=x; p[i].y=b[i]=y;
	}
	sort(a+1,a+n+1); sort(b+1,b+n+1);
	hh=unique(a+1,a+n+1)-a-1;
	ww=unique(b+1,b+n+1)-b-1;
	sort(p+1,p+n+1,cmpx);
	for(int i=1,j=0;i<=n;i+=1){
		while(j<hh&&a[j+1]==p[i].x) j+=1;
		v1[j].push_back(p[i].y);
	}
	sort(p+1,p+n+1,cmpy);
	for(int i=1,j=0;i<=n;i+=1){
		while(j<ww&&b[j+1]==p[i].y) j+=1;
		v2[j].push_back(p[i].x);
	}
	for(int i=1;i<=hh;i+=1){
		sort(v1[i].begin(),v1[i].end());
	}
	for(int i=1;i<=ww;i+=1){
		sort(v2[i].begin(),v2[i].end());
	}
	read(q);
	while(q--){
		scanf("%s",d); read(l);
		if(d[0]=='L'){
			rr=lower_bound(a+1,a+hh+1,r)-a;
			if(a[rr]!=r) lmt=0;
			else{
				it=lower_bound(v1[rr].begin(),v1[rr].end(),c);
				if(it==v1[rr].begin()) lmt=0;
				else --it,lmt=(*it);
			}
			c=max(c-l,lmt+1);
		}
		if(d[0]=='R'){
			rr=lower_bound(a+1,a+hh+1,r)-a;
			if(a[rr]!=r) lmt=w+1;
			else{
				it=upper_bound(v1[rr].begin(),v1[rr].end(),c);
				if(it==v1[rr].end()) lmt=w+1;
				else lmt=(*it);
			}
			c=min(c+l,lmt-1);
		}
		if(d[0]=='U'){
			cc=lower_bound(b+1,b+ww+1,c)-b;
			if(b[cc]!=c) lmt=0;
			else{
				it=lower_bound(v2[cc].begin(),v2[cc].end(),r);
				if(it==v2[cc].begin()) lmt=0;
				else --it,lmt=(*it);
			}
			r=max(r-l,lmt+1);
		}
		if(d[0]=='D'){
			cc=lower_bound(b+1,b+ww+1,c)-b;
			if(b[cc]!=c) lmt=h+1;
			else{
				it=upper_bound(v2[cc].begin(),v2[cc].end(),r);
				if(it==v2[cc].end()) lmt=h+1;
				else lmt=(*it);
			}
			r=min(r+l,lmt-1);
		}
		printf("%d %d\n",r,c);
	}
	return 0;
}
2022/10/15 21:54
加载中...