結果

問題 No.755 Zero-Sum Rectangle
ユーザー kenta255kenta255
提出日時 2019-07-26 09:48:01
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,147 bytes
コンパイル時間 2,378 ms
コンパイル使用メモリ 205,988 KB
実行使用メモリ 8,760 KB
最終ジャッジ日時 2023-09-15 00:14:00
合計ジャッジ時間 5,869 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
7,724 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
evil_1 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;
#define out(a) cout<<fixed<<setprecision((a))

template <typename T>
struct twodimBIT
{
// 1-indexed
// http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3095512#1
// https://www.slideshare.net/hcpc_hokudai/binary-indexed-tree
private:
	vector< vector<T> > array;
	const int n;
	const int m;

public:
	twodimBIT(int _n,int _m):
		array(_n+1,vector<T>(_m+1,0)), n(_n),m(_m){}

	// (1,1) ~ (x,y) ruisekiwa
	T sum(int x,int y) {
		T s = 0;
		for(int i=x;i>0;i-=i&(-i))
			for(int j=y;j>0;j-=j&(-j))
				s += array[i][j];
		return s;
	}

	// [(x1,y1),(x2,y2)] no souwa (x1<x2,y1<y2)
	T sum(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);
	}

	void add(int x,int y,T k) {
		for(int i=x;i<=n;i+=i&(-i))
			for(int j=y;j<=m;j+=j&(-j))
				array[i][j] += k;
	}
};

int main(){
	ll N,M;
	cin >> N >> M;
	twodimBIT<ll> bit(M,M);
	int ans[M+2][M+2] = {};
	FOR(i,1,M+1){
		FOR(j,1,M+1){
			ll k;
			cin >> k;
			bit.add(i,j,k);
		}
	}
	FOR(i,1,M+1)FOR(j,1,M+1)FOR(k,i,M+1)FOR(l,j,M+1){
		if(bit.sum(i,j,k,l)==0){
			ans[i][j]++;
			ans[k+1][l+1]++;
			ans[i][l+1]--;
			ans[k+1][j]--;
		}
	}
	FOR(i,1,M+1){
		FOR(j,1,M+1){
			ans[i][j+1]+=ans[i][j];
		}
	}
	FOR(j,1,M+1){
		FOR(i,1,M+1){
			ans[i+1][j]+=ans[i][j];
		}
	}
	FOR(i,0,N){
		ll x,y;
		cin >> x >> y;
		cout << ans[x][y] << endl;
	}
}
0