题目链接:GMOJ 2865
题目
题解
本题因为时间限制多开了十倍的原因,有多种解法。
解法A
思路
代码
#include<cstdio>
#include<algorithm>
using std::swap;
using std::sort;
using std::nth_element;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
register char ch=getchar();
register int res=0;
while(ch<'0'||'9'<ch)
ch=getchar();
while('0'<=ch&&ch<='9')
res=10*res+ch-'0',ch=getchar();
return res;
}
const int MAXN=60000+5;
const int MAXM=10000+5;
struct Node{
int x,y,z,ID;
void Read(int i){
ID=i;
x=read(),y=read(),z=read();
return;
}
bool operator<(const Node &a)const{
return z<a.z;
}
};
int n,m;
int ID[MAXN];
Node C[MAXN];
inline void QUERY(int,int,int,int,int);
inline void SWAP(int,int);
int main(void){
register int i;
n=read(),m=read();
for(i=1;i<=n;++i)
C[i].Read(i);
sort(C+1,C+n+1);
for(i=1;i<=n;++i)
ID[C[i].ID]=i;
for(i=1;i<=m;++i){
static char ch;
do{
ch=getchar();
}while(ch!='Q'&&ch!='S');
if(ch=='Q'){
static int lx,ly,rx,ry,k;
lx=read(),ly=read(),rx=read(),ry=read(),k=read();
//scanf("%d%d%d%d%d",&lx,&ly,&rx,&ry,&k);
QUERY(lx,ly,rx,ry,k);
}
if(ch=='S'){
static int a,b;
a=read(),b=read();
//scanf("%d%d",&a,&b);
SWAP(a+1,b+1);
}
}
return 0;
}
inline void QUERY(int lx,int ly,int rx,int ry,int k){
register bool flag=false;
register int i,cnt=0;
if(rx<lx)
swap(lx,rx);
if(ry<ly)
swap(ly,ry);
for(i=1;i<=n;++i)
if(lx<=C[i].x&&C[i].x<=rx&&ly<=C[i].y&&C[i].y<=ry)
if(++cnt==k){
flag=true;
printf("%d\n",C[i].z);
break;
}
if(!flag)
puts("It doesn't exist.");
return;
}
inline void SWAP(int a,int b){
swap(C[ID[a]].x,C[ID[b]].x),
swap(C[ID[a]].y,C[ID[b]].y),
swap(ID[a],ID[b]);
return;
}
近期评论