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

Submission #15241579

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<N; 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:15:15+0900 C - 宝探し 2 betrue12 C++ (GCC 9.2.1) 0 2326 Byte RE 206 ms 104464 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 0 / 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 8 ms 3752 KB
00-sample-01 2 ms 3708 KB
10-random_small-00 108 ms 3316 KB
10-random_small-01 5 ms 3832 KB
10-random_small-02 28 ms 3744 KB
10-random_small-03 105 ms 3456 KB
10-random_small-04 104 ms 3608 KB
10-random_small-05 129 ms 4944 KB
10-random_small-06 109 ms 3704 KB
10-random_small-07 105 ms 4056 KB
10-random_small-08 26 ms 8244 KB
20-random_large-00 206 ms 104376 KB
20-random_large-01 203 ms 104360 KB
20-random_large-02 204 ms 104216 KB
20-random_large-03 203 ms 104348 KB
20-random_large-04 202 ms 104464 KB
30-max_query-00 203 ms 104352 KB
30-max_query-01 203 ms 104464 KB
30-max_query-02 203 ms 104464 KB