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)
    
    void add(int h,int w,int x){
        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]--;
            bi[S[i][j]].add(i+1,j+1,1);
        }
    }
    
    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){
            bi[S[h1][w1]].add(h1+1,w1+1,-1);
            bi[S[h2][w2]].add(h2+1,w2+1,-1);
            
            swap(S[h1][w1],S[h2][w2]);
            
            bi[S[h1][w1]].add(h1+1,w1+1,1);
            bi[S[h2][w2]].add(h2+1,w2+1,1);
        }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
Task C - 宝探し 2
User Rubikun
Language C++ (GCC 9.2.1)
Score 100
Code Size 2905 Byte
Status
Exec Time 3669 ms
Memory 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