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
Task C - 宝探し 2
User betrue12
Language C++ (GCC 9.2.1)
Score 0
Code Size 2326 Byte
Status
Exec Time 206 ms
Memory 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