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