Contest Duration: ~ (local time) (90 minutes)

Submission #15536803

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=1000000007,MAX=105,INF=1<<30;

struct BIT2D{
vector<vector<int>> bit;
int H,W;
//1-indexed

void init(int h_,int w_){
H=h_;
W=w_;
h_*=2;
w_*=2;
for(int i=30;i>=0;i--){
if(h_&(1<<i)){
h_=1<<i;
h_++;
break;
}
}
for(int j=30;j>=0;j--){
if(w_&(1<<j)){
w_=1<<j;
w_++;
break;
}
}
bit.resize(h_);
for(int i=0;i<h_;i++) bit[i].assign(w_,0);
}

int sum(int h,int w){
int s=0;
while(h>0){
int ww=w;
while(w>0){
s+=bit[h][w];
w-=w&-w;
}
h-=h&-h;
w=ww;
}
return s;
}

int query(int h1,int h2,int w1,int w2){
return sum(h2,w2)+sum(h1-1,w1-1)-sum(h2,w1-1)-sum(h1-1,w2);
}

//[h1,h2][w1,w2]の和(1-indexed)

while(h<=H){
int ww=w;
while(w<=W){
bit[h][w]+=x;
w+=w&-w;
}
h+=h&-h;
w=ww;
}
}

//1-indexed
};

int main(){

std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);

int H,W,K;cin>>H>>W>>K;
vector<BIT2D> bi(K);
for(int i=0;i<K;i++) bi[i].init(H,W);
vector<vector<int>> S(H,vector<int>(W));

for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
cin>>S[i][j];
S[i][j]--;
}
}

int Q;cin>>Q;

while(Q--){
int t,h1,w1,h2,w2;cin>>t>>h1>>w1>>h2>>w2;
h1--;w1--;h2--;w2--;

if(t==1){

swap(S[h1][w1],S[h2][w2]);

}else{
pair<int,int> ans={-1,-1};

for(int k=0;k<K;k++){
pair<int,int> a=mp(bi[k].query(h1+1,h2+1,w1+1,w2+1),k+1);
chmax(ans,a);
}

cout<<ans.se<<" "<<ans.fi<<"\n";
}
}
}

#### Submission Info

Submission Time 2020-07-30 20:04:16+0900 C - 宝探し 2 Rubikun C++ (GCC 9.2.1) 100 2905 Byte AC 3669 ms 108792 KB

#### Judge Result

Set Name Score / Max Score Test Cases
All 100 / 100 00-sample-00, 00-sample-01, 10-random_small-00, 10-random_small-01, 10-random_small-02, 10-random_small-03, 10-random_small-04, 10-random_small-05, 10-random_small-06, 10-random_small-07, 10-random_small-08, 20-random_large-00, 20-random_large-01, 20-random_large-02, 20-random_large-03, 20-random_large-04, 30-max_query-00, 30-max_query-01, 30-max_query-02
Case Name Status Exec Time Memory
00-sample-00 6 ms 3500 KB
00-sample-01 6 ms 3480 KB
10-random_small-00 46 ms 3620 KB
10-random_small-01 7 ms 3628 KB
10-random_small-02 40 ms 3816 KB
10-random_small-03 11 ms 3512 KB
10-random_small-04 63 ms 3844 KB
10-random_small-05 228 ms 5508 KB
10-random_small-06 11 ms 3876 KB
10-random_small-07 47 ms 4244 KB
10-random_small-08 25 ms 10612 KB
20-random_large-00 2191 ms 108572 KB
20-random_large-01 2141 ms 108748 KB
20-random_large-02 2112 ms 108684 KB
20-random_large-03 2113 ms 108792 KB
20-random_large-04 2138 ms 108728 KB
30-max_query-00 3669 ms 108740 KB
30-max_query-01 3667 ms 108664 KB
30-max_query-02 3632 ms 108612 KB