bingoyes @ 2019-07-19 11:45:36
本地毫无问题,变量名,数组,头文件。。。等都考虑了, 一交全线RE
//#include <iostream>
#include <cstdio>
//#include <cstring>
#include <algorithm>
//#include <cmath>
#define R(a,b,c) for(register int a = (b); a <= (c); ++ a)
#define nR(a,b,c) for(register int a = (b); a >= (c); -- a)
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Swap(a,b) a^=b^=a^=b
#define ll long long
//#define ON_DEBUG
#ifdef ON_DEBUG
#define D_e_Line printf("\n\n----------\n\n")
#define D_e(x) cout << #x << " = " << x << endl
#define Pause() system("pause")
#else
#define D_e_Line ;
#endif
struct ios{
template<typename ATP>ios& operator >> (ATP &x){
x = 0; int f = 1; char c;
for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
x*= f;
return *this;
}
}io;
using namespace std;
const int N = 507;
const int M = 60007;
int n;
struct Matrix{
int x, y, val;
bool operator < (const Matrix &com) const{
return val < com.val;
}
}mp[N*N];
int cnt;
struct Questions{
int xx1, yy1, xx2, yy2, K;
}q[M];
int t[N][N];
inline void Updata(int x, int y, int val){
for(register int i = x; i <= n; i += i&-i)
for(register int j = y; j <= n; j += j&-j)
t[i][j] += val;
}
inline int Query(int x, int y){
int s = 0;
for(register int i = x; i; i -= i&-i)
for(register int j = y; j; j -= j&-j)
s += t[i][j];
return s;
}
// I don't know what happend below
//inline void Updata(int x, int y, int val){
// for(; x <= n; x += x&-x)
// for(; y <= n; y += y&-y)
// t[x][y] += val;
//}
//inline int Query(int x, int y){
// int s = 0;
// for(; x; x -= x&-x)
// for(; y; y -= y&-y)
// s += t[x][y];
// return s;
//}
inline int Calc(int xx1, int yy1, int xx2, int yy2){
return Query(xx2, yy2)-Query(xx2, yy1-1)-Query(xx1-1, yy2)+Query(xx1-1, yy1-1);
}
int id[N],siz[N],ans[N];
int tmp[N], tmp1[N], tmp2[N];
inline void Dictomy(int l, int r, int L, int R){
if(L > R) return;
if(l == r){
R(i,L,R)
ans[id[i]] = mp[l].val;
return;
}
int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
R(i,l,mid) Updata(mp[i].x, mp[i].y, 1);
R(i,L,R){
int sum = Calc(q[id[i]].xx1, q[id[i]].yy1, q[id[i]].xx2, q[id[i]].yy2);
if(siz[id[i]]+sum >= q[id[i]].K){
tmp1[++cnt1] = id[i];
}
else{
siz[id[i]] += sum;
tmp2[++cnt2] = id[i];
}
}
R(i,l,mid) Updata(mp[i].x, mp[i].y, -1);
int qCnt = L-1;
R(i,1,cnt1){
tmp[++qCnt] = tmp1[i];
id[qCnt] = tmp[qCnt];
}
R(i,1,cnt2){
tmp[++qCnt] = tmp2[i];
id[qCnt] = tmp[qCnt];
}
Dictomy(l, mid, L, L + cnt1 - 1);
Dictomy(mid + 1, r, L + cnt1, R);
}
//#define FileInTheHole
int main(){
//#ifdef FileInTheHole
// D_e_Line;
// freopen("in.txt", "r", stdin);
//#endif
int Que;
io >> n >> Que;
R(i,1,n){
R(j,1,n){
int x;
io >> x;
mp[++cnt] = (Matrix){i, j, x};
}
}
sort(mp + 1, mp + cnt + 1);
R(i,1,Que){
io >> q[i].xx1 >> q[i].yy1 >> q[i].xx2 >> q[i].yy2 >> q[i].K;
id[i] = i;
}
Dictomy(1, cnt, 1, Que);
R(i,1,Que)
printf("%d\n", ans[i]);
return 0;
}
by huyang2007 @ 2019-07-19 11:54:46
还说是萌新 ,明明是大佬
by bingoyes @ 2019-07-19 13:53:15
@huyang2007 I am very vegetable。帮弱小无助的我看看吧
by Kushina_Anna @ 2019-07-19 13:53:42
@bingoyes 大佬orz
by huyang2007 @ 2019-07-19 15:11:11
@bingoyes
你认为我这个蓝名能帮你?
by apocryphal @ 2019-08-28 10:20:50
@bingoyes ans
数组的大小应该是M
吧。。。终于找到一个和我一样的人了qwq
by apocryphal @ 2019-08-28 10:23:35
@bingoyes 还有 qndmx