Submission #14065206


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 A - eject
User mtsd
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3822 Byte
Status
Exec Time 100 ms
Memory 256 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, 10-random_small-09, 20-random_large-00, 20-random_large-01, 20-random_large-02, 20-random_large-03, 20-random_large-04, 20-random_large-05, 20-random_large-06, 20-random_large-07, 20-random_large-08, 20-random_large-09, 30-p_zero-00, 30-p_zero-01, 30-p_zero-02, 30-p_zero-03, 30-p_zero-04, 40-p_one-00, 40-p_one-01, 40-p_one-02, 40-p_one-03, 40-p_one-04, 90-handmade-00
Case Name Status Exec Time Memory
00-sample-00 100 ms 256 KB
00-sample-01 100 ms 256 KB
10-random_small-00 99 ms 256 KB
10-random_small-01 99 ms 256 KB
10-random_small-02 98 ms 256 KB
10-random_small-03 99 ms 256 KB
10-random_small-04 99 ms 256 KB
10-random_small-05 99 ms 256 KB
10-random_small-06 100 ms 256 KB
10-random_small-07 100 ms 256 KB
10-random_small-08 99 ms 256 KB
10-random_small-09 100 ms 256 KB
20-random_large-00 100 ms 256 KB
20-random_large-01 99 ms 256 KB
20-random_large-02 100 ms 256 KB
20-random_large-03 99 ms 256 KB
20-random_large-04 99 ms 256 KB
20-random_large-05 99 ms 256 KB
20-random_large-06 99 ms 256 KB
20-random_large-07 98 ms 256 KB
20-random_large-08 99 ms 256 KB
20-random_large-09 99 ms 256 KB
30-p_zero-00 100 ms 256 KB
30-p_zero-01 98 ms 256 KB
30-p_zero-02 98 ms 256 KB
30-p_zero-03 99 ms 256 KB
30-p_zero-04 99 ms 256 KB
40-p_one-00 98 ms 256 KB
40-p_one-01 98 ms 256 KB
40-p_one-02 99 ms 256 KB
40-p_one-03 99 ms 256 KB
40-p_one-04 99 ms 256 KB
90-handmade-00 99 ms 256 KB