PKU 2019-Cornfields

問題概要

NxNの配列が与えられる。k個のクエリーに対して
xi<=x

解法

multisetを使って前計算する

実装(C++)

#include <cstdio>
#include <iostream>
#include <set>
using namespace std;
int N,B,K;
int MAP[250][250];
int min1[250][250];
int min2[250][250];
int max1[250][250];
int max2[250][250];
void show(int x[250][250]){

	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			cout<<x[i][j]<<" ";

		}
		cout<<endl;
	}
}
int main() {
	scanf("%d%d%d",&N,&B,&K);
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			scanf("%d",&MAP[i][j]);
		}
	}
	for(int i=0;i<N;i++){
		multiset<int> ss;
		for(int j=0;j<N;j++){
			ss.insert(MAP[i][j]);
			if(ss.size()>B){
				ss.erase(ss.find(MAP[i][j-B]));
			}
			if(ss.size()==B){
				min1[i][j-B+1]=*ss.begin();
				max1[i][j-B+1]=*ss.rbegin();
			}
		}
	}
	//show(min1);
	for(int j=0;j<=N-B;j++){
		multiset<int> ss;
		for(int i=0;i<N;i++){
			ss.insert(min1[i][j]);
//			cout<<"!"<<min1[i][j]<<endl;
			if(ss.size()>B){
				ss.erase(ss.find(min1[i-B][j]));
			}
			if(ss.size()==B){
				min2[i-B+1][j]=*ss.begin();
//				cout<<"!!"<<*ss.begin()<<endl;
			}
		}
	}
	for(int j=0;j<=N-B;j++){
		multiset<int> ss;
		for(int i=0;i<N;i++){
			ss.insert(max1[i][j]);
			if(ss.size()>B){
				ss.erase(ss.find(max1[i-B][j]));
			}
			if(ss.size()==B){
				max2[i-B+1][j]=*ss.rbegin();
			}
		}
	}
//	show(max2);
//	show(min2);
	for(int i=0;i<K;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		printf("%d\n",max2[a-1][b-1]-min2[a-1][b-1]);
	}
	return 0;
}