记录编号	357330	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]矩阵乘法	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	11.160 s
提交时间	2016-12-10 17:36:42	内存使用	28.96 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <list>
#include <queue>
#include <vector>
#include <string>
using namespace std;
namespace IO
{
char buf[1<<18], *fs, *ft;
inline char readc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin),fs==ft))?0:*fs++;
}
inline int fast_read()
{
    int r;
    char c;
    bool s = false;
    while(c = readc())
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }else if(c == '-')s = true;
    }
    while(isdigit(c = readc()))
        r = (r<<3)+(r<<1)+(c^0x30);
    return s?-r:r;
}

}using IO::fast_read;

#define MAXN 501
#define MAXQ 60001
class Fenwick2D   //二维树状数组
{
    int n, m;
    int bit[MAXN][MAXN];
public:
    void setd(int a, int b)
    {
        n = a, m = b;
        memset(bit, 0, sizeof(bit));
    }
    void add(int x, int y, int v)
    {
        if(!x)return;
        if(!x)puts("alert1");
        for(int i = x; i <= n; i += i&-i)
            for(int j = y; j <= m; j += j&-j)
                bit[i][j] += v;
    }
    int sum(int x, int y)
    {
        //if(!x)return 0;
        //if(!x)puts("alert2");
        int r = 0;
        for(int i = x; i; i -= i&-i)
            for(int j = y; j; j -= j&-j)
                r += bit[i][j];
        return r;
    }
    int query(int x1, int y1, int x2, int y2)
    {
        return sum(x2, y2)-sum(x1-1, y2)-sum(x2, y1-1)+sum(x1-1, y1-1);
    }
}fwt;
struct que
{
    int id, x1, y1, x2, y2, k;
}qs[MAXQ*6], s1[MAXQ*6], s2[MAXQ*6];
int ans[MAXQ*6], cnt[MAXQ*6];
void solve(int a, int b, int l, int r)
{
    if(a > b || l > r)return;
    if(l == r)
    {
        for(int i = a; i <= b; i++)ans[qs[i].id] = l;
        return;
    }
    int m = (l+r)>>1;
    int p1 = 0, p2 = 0;
    for(int i = a; i <= b; i++)
    {
        if(!qs[i].id)
        {
            if(qs[i].k <= m)
            {
                fwt.add(qs[i].x1, qs[i].y1, 1);
                s1[p1++] = qs[i];
            }else s2[p2++] = qs[i];
        }
        else
        {
            cnt[i] = fwt.query(qs[i].x1, qs[i].y1, qs[i].x2, qs[i].y2);
            if(cnt[i] >= qs[i].k)s1[p1++] = qs[i];
            else{
                qs[i].k -= cnt[i];
                s2[p2++] = qs[i];
            }
        }
    }
    for(int i = a; i <= b; i++)if(!qs[i].id && qs[i].k <= m)fwt.add(qs[i].x1, qs[i].y1, -1);
    for(int i = 0; i < p1; i++)qs[a+i] = s1[i];
    for(int i = 0; i < p2; i++)qs[a+p1+i] = s2[i];
    solve(a, a+p1-1, l, m);
    solve(a+p1, b, m+1, r);
}
int main()
{
    //freopen("test_data.txt", "r", stdin);
    freopen("nt2012_mat.in", "r", stdin);
    freopen("nt2012_mat.out", "w", stdout);
    int n, q;
    n = fast_read();
    q = fast_read();
    fwt.setd(n, n);
    int tot = 0;
    for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)
        qs[++tot] = (que){0, i, j, 0, 0, fast_read()};
    for(int i = 1; i <= q; i++)
    {
        que tq;
        tq.id = i;
        tq.x1 = fast_read();
        tq.y1 = fast_read();
        tq.x2 = fast_read();
        tq.y2 = fast_read();
        tq.k = fast_read();
        qs[++tot] = tq;
    }
    solve(1, tot, 0, 1e9);
    for(int i = 1; i <= q; i++)
        printf("%d\n", ans[i]);
    return 0;
}