結果

問題 No.755 Zero-Sum Rectangle
コンテスト
ユーザー kriii
提出日時 2018-12-09 01:29:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 64 ms / 2,000 ms
コード長 904 bytes
コンパイル時間 466 ms
コンパイル使用メモリ 48,084 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-15 07:00:21
合計ジャッジ時間 1,920 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <algorithm>
using namespace std;

int N,M; long long A[133][133],U[133][133];

int main()
{
	scanf ("%d %d",&N,&M);
	for (int i=1;i<=M;i++){
		for (int j=1;j<=M;j++){
			scanf ("%lld",&A[i][j]);
			A[i][j] += A[i-1][j] + A[i][j-1] - A[i-1][j-1];
		}
	}

	for (int i1=1;i1<=M;i1++) for (int i2=i1;i2<=M;i2++){
		pair<long long, int> X[133];
		X[0] = {0,1};
		for (int j=1;j<=M;j++) X[j] = {A[i2][j] - A[i1-1][j], j+1};
		sort(X,X+M+1);

		for (int j=0;j<=M;){
			int k = j;
			while (k <= M && X[j].first == X[k].first) k++;
			for (int l=j;l<k;l++){
				int d = (k - l - 1) - (l - j);
				int r = X[l].second;
				U[i1][r] += d;
				U[i2+1][r] -= d;
			}
			j = k;
		}
	}

	for (int i=1;i<=M;i++){
		for (int j=1;j<=M;j++){
			U[i][j] += U[i-1][j] + U[i][j-1] - U[i-1][j-1];
		}
	}

	while (N--){
		int x,y; scanf ("%d %d",&x,&y);
		printf ("%lld\n",U[x][y]);
	}

	return 0;
}
0