Submission #14065109


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<vector<vector<int> > >aa(k,vector<vector<int>>(n,vector<int>(m)));
    
    rep(i,n){
        rep(j,m){
            int t;
            cin >> t;
            t--;
            s[i][j] = t;
            aa[t][i][j] = 1;
        }
    }
    vector<BIT<int> > bit;
    rep(i,k){
        // cerr << i << endl;
        BIT<int> tmp(aa[i]);
        bit.push_back(tmp);
    }
    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 4000 Byte
Status
Exec Time 5268 ms
Memory 204288 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 2 ms 512 KB
00-sample-01 1 ms 256 KB
10-random_small-00 222 ms 384 KB
10-random_small-01 7 ms 256 KB
10-random_small-02 83 ms 512 KB
10-random_small-03 21 ms 384 KB
10-random_small-04 261 ms 768 KB
10-random_small-05 593 ms 2944 KB
10-random_small-06 26 ms 640 KB
10-random_small-07 164 ms 1280 KB
10-random_small-08 55 ms 8960 KB
20-random_large-00 3775 ms 201984 KB
20-random_large-01 3821 ms 201984 KB
20-random_large-02 3772 ms 201984 KB
20-random_large-03 3785 ms 203904 KB
20-random_large-04 3800 ms 201984 KB
30-max_query-00 5267 ms 203904 KB
30-max_query-01 5267 ms 204288 KB
30-max_query-02 5268 ms 202240 KB