记录编号	455399	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]矩阵乘法	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	6.901 s
提交时间	2017-10-02 07:22:51	内存使用	6.26 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int read() {
	int s=0,f=1;
	char ch=getchar();
	for( ; ch<'0'||ch>'9'; f=(ch=='-')?-1:f,ch=getchar()) ;
	for( ; ch>='0'&&ch<='9'; s=s*10+(ch^48),ch=getchar()) ;
	return s*f;
}
int n,q,cnt,Single[505][505],sum[505][505],nxt[60005],pre[60005];
struct Query {
	int Up,Down,Left,Right,k,ans;
} query[60005];
struct Blo {
	int x,y,val;
	friend bool operator < (Blo a,Blo b) {
		return a.val<b.val;
	}
} blo[250002];
int Main() {
	freopen("nt2012_mat.in","r",stdin);
	freopen("nt2012_mat.out","w",stdout);
	n=read(),q=read();
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=n; ++j) blo[++cnt].x=i,blo[cnt].y=j,blo[cnt].val=read();
	}
	sort(blo+1,blo+cnt+1);
	for(int i=1; i<=q; ++i) {
		query[i].Up=read(),query[i].Left=read(),query[i].Down=read(),query[i].Right=read(),query[i].k=read();
		pre[i]=i-1,nxt[i]=i+1;
	}
	nxt[0]=1;
	for(int j=1,i=1; i<=n; ++i) {
		for( ; j<=i*n; ++j) Single[blo[j].x][blo[j].y]=1;
		for(int k=1; k<=n; ++k) {
			for(int h=1; h<=n; ++h) sum[k][h]=sum[k-1][h]+sum[k][h-1]-sum[k-1][h-1]+Single[k][h];
		}
		for(int h=nxt[0]; h<=q; h=nxt[h]) {
			int Up=query[h].Up,Down=query[h].Down,Left=query[h].Left,Right=query[h].Right,k=query[h].k;
			if(sum[Down][Right]-sum[Down][Left-1]-sum[Up-1][Right]+sum[Up-1][Left-1]<k) continue;
			else {
				int now=sum[Down][Right]-sum[Down][Left-1]-sum[Up-1][Right]+sum[Up-1][Left-1];
				for(int g=i*n; g>=(i-1)*n; --g) {
					if(Up<=blo[g].x&&blo[g].x<=Down&&Left<=blo[g].y&&blo[g].y<=Right) {
						--now;
						if(now<k) {
							query[h].ans=blo[g].val;
							nxt[pre[h]]=nxt[h];
							pre[nxt[h]]=pre[h];
							break;
						}
					}
				}
			}
		}
	}
	for(int i=1; i<=q; ++i) printf("%d\n",query[i].ans);
	return 0;
}
int hehe=Main();
int main() {
	;
}