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

Submission #15241597

Source Code Expand

Copy
```#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct BIT {
int n;
vector<T> dat;

BIT(int n=0){
initialize(n);
}

void initialize(int nin){
n = nin;
dat.assign(n, 0);
}

T sum(int i){
T s = 0;
while(i >= 0){
s += dat[i];
i = (i & (i+1)) - 1;
}
return s;
}

T sum_between(int i, int j){
return sum(j) - sum(i-1);
}

void plus(int i, T x){
while(i < n){
dat[i] += x;
i |= i+1;
}
}
};

template<typename T>
struct BIT2D {
int n;
vector<BIT<T>> dat;

BIT2D(){}
BIT2D(int nin, int min){
n = nin;
dat.assign(n, 0);
for(int i=0; i<n; i++) dat[i] = BIT<T>(min);
}

T sum(int i, int js, int jt){
T s = 0;
while(i >= 0){
s += dat[i].sum_between(js, jt);
i = (i & (i+1)) - 1;
}
return s;
}

T sum_between(int is, int it, int js, int jt){
return sum(it, js, jt) - sum(is-1, js, jt);
}

void plus(int i, int j, T x){
while(i < n){
dat[i].plus(j, x);
i |= i+1;
}
}
};

int main(){
int N, M, K;
cin >> N >> M >> K;
int A[500][500];
for(int i=0; i<N; i++) for(int j=0; j<M; j++) scanf("%d", &A[i][j]), A[i][j]--;

BIT2D<int> bit[100];
for(int k=0; k<K; k++) bit[k] = BIT2D<int>(N, M);
for(int i=0; i<N; i++) for(int j=0; j<M; j++) bit[A[i][j]].plus(i, j, 1);

int Q;
cin >> Q;
while(Q--){
int t, x1, y1, x2, y2;
scanf("%d %d %d %d %d", &t, &x1, &y1, &x2, &y2);
x1--; y1--; x2--; y2--;
if(t == 1){
bit[A[x1][y1]].plus(x1, y1, -1);
bit[A[x2][y2]].plus(x2, y2, -1);
swap(A[x1][y1], A[x2][y2]);
bit[A[x1][y1]].plus(x1, y1, 1);
bit[A[x2][y2]].plus(x2, y2, 1);
}else{
int v = -1, i = 0;
for(int k=0; k<K; k++){
int v2 = bit[k].sum_between(x1, x2, y1, y2);
if(v <= v2) v = v2, i = k;
}
printf("%d %d\n", i+1, v);
}
}

return 0;
}
```

#### Submission Info

Submission Time 2020-07-14 21:16:28+0900 C - 宝探し 2 betrue12 C++ (GCC 9.2.1) 100 2326 Byte AC 4124 ms 104708 KB

#### Compile Error

```./Main.cpp: In function ‘int main()’:
./Main.cpp:76:56: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
76 |     for(int i=0; i<N; i++) for(int j=0; j<M; j++) scanf("%d", &A[i][j]), A[i][j]--;
|                                                   ~~~~~^~~~~~~~~~~~~~~~
./Main.cpp:86:14: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
86 |         scanf("%d %d %d %d %d", &t, &x1, &y1, &x2, &y2);
|         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
```

#### 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 7 ms 3672 KB
00-sample-01 3 ms 3688 KB
10-random_small-00 38 ms 3740 KB
10-random_small-01 11 ms 3656 KB
10-random_small-02 39 ms 3832 KB
10-random_small-03 12 ms 3868 KB
10-random_small-04 60 ms 3888 KB
10-random_small-05 229 ms 4992 KB
10-random_small-06 13 ms 4068 KB
10-random_small-07 45 ms 4268 KB
10-random_small-08 26 ms 8356 KB
20-random_large-00 2378 ms 104600 KB
20-random_large-01 2412 ms 104652 KB
20-random_large-02 2357 ms 104708 KB
20-random_large-03 2377 ms 104604 KB
20-random_large-04 2360 ms 104708 KB
30-max_query-00 4124 ms 104708 KB
30-max_query-01 4112 ms 104636 KB
30-max_query-02 4037 ms 104640 KB