xiaolilsq @ 2020-02-11 17:40:24
评测情况
程序:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<typename T>void read(T &x){
x=0;int f(1);char c(getchar());
for(;!isdigit(c);c=getchar())if(c=='-')f=-f;
for(; isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c-'0');
x*=f;
}
template<typename T>void write(T x){
if(x<0)putchar('-'),x=-x;
if(x/10)write(x/10),x%=10;
putchar(x+'0');
}
const int maxn=707,maxq=100006;
int n;
struct tree{
int a[maxn][maxn];
int lowbit(int x){
return x&-x;
}
void add(int l,int r,int v){
for(int x=l;x<=n;x+=lowbit(x))
for(int y=r;y<=n;y+=lowbit(y))
a[x][y]+=v;
}
int query(int l,int r){
int ans=0;
for(int x=l;x;x-=lowbit(x))
for(int y=r;y;y-=lowbit(y))
ans+=a[x][y];
return ans;
}
}T;
long long va[maxn*maxn];
struct _1{
int X,Y,val;
}_1_[maxn*maxn],_11[maxn*maxn],_12[maxn*maxn];
struct _2{
int X1,X2,Y1,Y2,k,num;
}_2_[maxq],_21[maxq],_22[maxq];
int ans[maxq];
void solve(int tl,int tr,int l,int r,int L,int R){
if(L>R)return;
if(tl==tr){
for(int i=L;i<=R;++i){
ans[_2_[i].num]=va[tl];
}
return;
}
int mid=tl+tr>>1,_11cn=0,_12cn=0,_21cn=0,_22cn=0;
for(int i=l;i<=r;++i){
if(_1_[i].val<=mid){
T.add(_1_[i].X,_1_[i].Y,1);
_11[_11cn++]=_1_[i];
}
else{
_12[_12cn++]=_1_[i];
}
}
for(int i=L;i<=R;++i){
int k=T.query(_2_[i].X2,_2_[i].Y2)+T.query(_2_[i].X1-1,_2_[i].Y1-1)
-T.query(_2_[i].X1-1,_2_[i].Y2)-T.query(_2_[i].X2,_2_[i].Y1-1);
if(_2_[i].k<=k){
_21[_21cn++]=_2_[i];
}
else{
_2_[i].k-=k;
_22[_22cn++]=_2_[i];
}
}
for(int i=0;i<_11cn;++i)
T.add(_11[i].X,_11[i].Y,-1);
for(int i=0;i<_11cn;++i)_1_[l+i]=_11[i];
for(int i=0;i<_12cn;++i)_1_[l+_11cn+i]=_12[i];
for(int i=0;i<_21cn;++i)_2_[L+i]=_21[i];
for(int i=0;i<_22cn;++i)_2_[L+_21cn+i]=_22[i];
solve(tl,mid,l,l+_11cn-1,L,L+_21cn-1);
solve(mid+1,tr,l+_11cn,r,L+_21cn,R);
}
int main(){
read(n);int q,cnt=0,vc=0;read(q);
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
_1_[cnt].X=i;_1_[cnt].Y=j;
read(_1_[cnt].val);
va[vc++]=_1_[cnt].val;
++cnt;
}
}
sort(va,va+vc);vc=unique(va,va+vc)-va;
for(int i=1;i<=n*n;++i)
_1_[i].val=lower_bound(va,va+vc,_1_[i].val)-va;
for(int i=0;i<q;++i){
read(_2_[i].X1);
read(_2_[i].Y1);
read(_2_[i].X2);
read(_2_[i].Y2);
read(_2_[i].k);
_2_[i].num=i;
}
solve(0,vc-1,0,cnt-1,0,q-1);
for(int i=0;i<q;++i)write(ans[i]),putchar('\n');
return 0;
}
求各位大佬帮忙查错,感谢
by 春日野悠 @ 2020-02-11 17:43:49
%%%
by xiaolilsq @ 2020-02-11 17:47:09
查了好久了,就是找不到问题
by xiaolilsq @ 2020-04-23 14:12:37
找到错误了。
by Develop @ 2020-05-05 22:15:43
%%%%