Submission #15211702


Source Code Expand

Copy
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))

using namespace std;
typedef pair<llint, llint> P;

int h, w, k, Q;
int a[505][505], sum[105][505][505];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> h >> w >> k;
	for(int y = 1; y <= h; y++){
		for(int x = 1; x <= w; x++){
			cin >> a[x][y];
		}
	}
	
	for(int i = 1; i <= k; i++){
		for(int x = 1; x <= w; x++){
			for(int y = 1; y <= h; y++){
				sum[i][x][y] = sum[i][x-1][y] + sum[i][x][y-1] - sum[i][x-1][y-1];
				if(a[x][y] == i) sum[i][x][y]++;
			}
		}
	}
	
	cin >> Q;
	llint t, lx, ly, rx, ry;
	for(int q = 1; q <= Q; q++){
		cin >> t >> ly >> lx >> ry >> rx;
		if(t == 1){
			if(lx > rx) swap(lx, rx);
			if(ly > ry) swap(ly, ry);
			if(a[lx][ly] == a[rx][ry]) continue;
			if(lx == rx){
				for(int i = lx; i <= w; i++) sum[a[lx][ly]][i][ly]--;
				for(int i = lx; i <= w; i++) sum[a[rx][ry]][i][ly]++;
			}
			else{
				for(int i = ly; i <= h; i++) sum[a[lx][ly]][lx][i]--;
				for(int i = ly; i <= h; i++) sum[a[rx][ry]][lx][i]++;
			}
			swap(a[lx][ly], a[rx][ry]);
		}
		else{
			P p = P(0, 0);
			for(int i = 1; i <= k; i++){
				llint res = sum[i][rx][ry] - sum[i][lx-1][ry] - sum[i][rx][ly-1] + sum[i][lx-1][ly-1];
				p = max(p, P(res, i));
			}
			cout << p.second << " " << p.first << endl;
		}
	}
	
	return 0;
}

Submission Info

Submission Time
Task C - 宝探し 2
User leaf1415
Language C++ (GCC 9.2.1)
Score 100
Code Size 1880 Byte
Status
Exec Time 600 ms
Memory 103560 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 3532 KB
00-sample-01 4 ms 3508 KB
10-random_small-00 96 ms 3588 KB
10-random_small-01 10 ms 3824 KB
10-random_small-02 46 ms 5648 KB
10-random_small-03 14 ms 3904 KB
10-random_small-04 101 ms 4608 KB
10-random_small-05 168 ms 13632 KB
10-random_small-06 17 ms 4340 KB
10-random_small-07 64 ms 5728 KB
10-random_small-08 29 ms 23672 KB
20-random_large-00 540 ms 103552 KB
20-random_large-01 533 ms 103516 KB
20-random_large-02 536 ms 103520 KB
20-random_large-03 533 ms 103560 KB
20-random_large-04 535 ms 103528 KB
30-max_query-00 594 ms 103496 KB
30-max_query-01 595 ms 103492 KB
30-max_query-02 600 ms 103524 KB