Submission #14065180


Source Code Expand

Copy
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
 
template<class T> inline bool chmax(T &a, T b){
    if(a<b){
        a = b;
        return true;
    }
    return false;
}

template<class T> inline bool chmin(T &a, T b){
    if(a>b){
        a = b;
        return true;
    }
    return false;
}
template<typename T> class BIT {
private:
    int n,m; vector<vector<T> > bit;
public:
    void add(int i, int j, T val){
        for(int i_ = i+1; i_ < n; i_ += i_ & -i_)
            for(int j_ = j+1; j_ < m; j_ += j_ & -j_)
                bit[i_][j_] += val;
    }
    T sum(int i, int j){
        T s = 0;
        for(int i_ = i+1; i_ > 0; i_ -= i_ & -i_)
            for(int j_ = j+1; j_ > 0; j_ -= j_ & -j_)
                s += bit[i_][j_];
        return s;
    }
    T sum(int lx, int rx, int ly, int ry){
        return sum(rx-1, ry-1) - sum(lx-1, ry-1) - sum(rx-1, ly-1) + sum(lx-1, ly-1);
    }
    BIT(int sz1, int sz2){
        n = sz1 + 1, m = sz2 + 1;
        bit.resize(n, vector<T>(m, 0));
    }
    BIT(vector<vector<T> >& v){
        n = (int)v.size()+1, m = (int)v[0].size()+1;
        bit.resize(n, vector<T>(m, 0));
        for(int i = 0; i < n-1; i++)
            for(int j = 0; j < m-1; j++)
                add(i, j, v[i][j]);
    }
    void print(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cout<< sum(i-1, i, j-1, j) << " ";
            }
            cout << "\n";
        }
    }
    void print_sum(){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cout<< sum(i-1, j-1) << " ";
            }
            cout << "\n";
        }
    }
};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m,k;
    cin >> n >> m >> k;
    vector<vector<int> > s(n,vector<int>(m));
    vector<BIT<int> > bit(k,BIT<int>(n,m));
    rep(i,n){
        rep(j,m){
            int t;
            cin >> t;
            t--;
            s[i][j] = t;
            bit[t].add(i,j,1);
        }
    }
    int q;
    cin >> q;
    rep(i,q){
        int p,a,b,c,d;
        cin >> p >> a >> b >> c >> d;
        a--;b--;c--;d--;
        if(p==1){
            if(s[a][b]!=s[c][d]){
                bit[s[a][b]].add(a,b,-1);
                bit[s[a][b]].add(c,d,1);
                bit[s[c][d]].add(a,b,1);
                bit[s[c][d]].add(c,d,-1);
                swap(s[a][b],s[c][d]);
            }
        }else{
            int mx = 0;
            int res = 0;
            rep(j,k){
                int tmp = bit[j].sum(a,c+1,b,d+1);
                // cerr << j << " " << a << " " << b <<" " << c << " " << d << " " << endl;
                // bit[j].print();
                // cerr << tmp << endl;
                if(mx<=tmp){
                    mx = tmp;
                    res = j+1;
                }
            }
            cout << res << " " << mx << "\n";
        }
    }
    return 0;
}

Submission Info

Submission Time
Task C - 宝探し 2
User mtsd
Language C++14 (Clang 3.8.0)
Score 0
Code Size 3822 Byte
Status
Exec Time 5262 ms
Memory 104448 KB

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 9 ms 888 KB
00-sample-01 1 ms 256 KB
10-random_small-00 223 ms 512 KB
10-random_small-01 7 ms 256 KB
10-random_small-02 82 ms 384 KB
10-random_small-03 21 ms 384 KB
10-random_small-04 257 ms 640 KB
10-random_small-05 585 ms 1792 KB
10-random_small-06 25 ms 512 KB
10-random_small-07 162 ms 896 KB
10-random_small-08 33 ms 4736 KB
20-random_large-00 3217 ms 102400 KB
20-random_large-01 3056 ms 104320 KB
20-random_large-02 3061 ms 102400 KB
20-random_large-03 3131 ms 102400 KB
20-random_large-04 3062 ms 104192 KB
30-max_query-00 5189 ms 102656 KB
30-max_query-01 5262 ms 102656 KB
30-max_query-02 5151 ms 104448 KB