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; }