Contest Duration: ~ (local time) (90 minutes)

Submission #15573873

Source Code Expand

Copy
```#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef int ll;
typedef long double ld;
using namespace std;

struct segtree {
ll H, W, INF = 1000000000;
vvl dat;
segtree(ll h, ll w, ll num) {
H = W = 1;
while(H < h) H <<= 1;
while(W < w) W <<= 1;
dat.assign(2*H-1,vll(2*W-1,num));
}
void insert(ll i, ll j, ll x){
i+=H-1, j+=W-1;
dat[i][j] = x;
ll tmp_i = i;
while(tmp_i>0){
tmp_i = (tmp_i-1)/2;
dat[tmp_i][j] = dat[tmp_i*2+1][j] + dat[tmp_i*2+2][j];
}
ll tmp_j = j;
while(tmp_j>0){
tmp_j = (tmp_j-1)/2;
dat[i][tmp_j] = dat[i][tmp_j*2+1] + dat[i][tmp_j*2+2];
}
while(i>0){
i = (i-1)/2;
tmp_j = j;
while(tmp_j>0){
tmp_j = (tmp_j-1)/2;
dat[i][tmp_j] = dat[i][tmp_j*2+1] + dat[i][tmp_j*2+2];
}
}
}
ll find(int a, int b, int A, int B) { return find_h(a,b,A,B,0,H,0); }
ll find_h(int a, int b, int A, int B, int l, int r, int k) {
if(r<=a||b<=l) return 0;
if(a<=l&&r<=b) return find_w(A,B,0,W,k,0);
return find_h(a,b,A,B,l,(l+r)/2,2*k+1) + find_h(a,b,A,B,(l+r)/2,r,2*k+2);
}
ll find_w(int A, int B, int l, int r, int i, int k) {
if(r<=A||B<=l) return 0;
if(A<=l&&r<=B) return dat[i][k];
return find_w(A,B,l,(l+r)/2,i,2*k+1) + find_w(A,B,(l+r)/2,r,i,2*k+2);
}
};

int main(int argc, char const *argv[]) {
ll n, m, k;std::cin >> n >> m >> k;
vvl d = VV(n, m, 0, ll);
vector<segtree> seg(k, segtree(n, m, 0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
ll a;scanf("%d", &a);a--;
d[i][j] = a;
seg[a].insert(i, j, 1);
}
}

ll q;std::cin >> q;
for(int i=0;i<q;i++){
ll t;std::cin >> t;
if(t==1){
ll a, b, x, y;scanf("%d %d %d %d", &a, &b, &x, &y);
a--, b--, x--, y--;
ll f = d[a][b], s = d[x][y];
seg[f].insert(a, b, 0);
seg[f].insert(x, y, 1);
seg[s].insert(x, y, 0);
seg[s].insert(a, b, 1);
swap(d[a][b], d[x][y]);
}else{
ll a, b, x, y;scanf("%d %d %d %d", &a, &b, &x, &y);
a--, b--, x--, y--;
ll ans = -1, ar = -1;
for(int i=0;i<k;i++){
ll q = seg[i].find(a, x+1, b, y+1);
if(ans <= q) ans = q, ar = i+1;
}
std::cout << ar << " " << ans << '\n';
}
}
return 0;
}
```

#### Submission Info

Submission Time 2020-08-02 03:30:58+0900 C - 宝探し 2 tonegawa C++ (GCC 9.2.1) 0 2941 Byte WA 5526 ms 421808 KB

#### Compile Error

```./Main.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization ("O3")
|
./Main.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
3 | #pragma GCC optimization ("unroll-loops")
|
./Main.cpp: In function ‘int main(int, const char**)’:
./Main.cpp:71:14: warning: unused parameter ‘argc’ [-Wunused-parameter]
71 | int main(int argc, char const *argv[]) {
|          ~~~~^~~~
./Main.cpp:71:32: warning: unused parameter ‘argv’ [-Wunused-parameter]
71 | int main(int argc, char const *argv[]) {
|                    ~~~~~~~~~~~~^~~~~~
./Main.cpp:77:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
77 |       ll a;scanf("%d", &a);a--;
|            ~~~~~^~~~~~~~~~
./Main.cpp:87:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
87 |       ll a, b, x, y;scanf("%d %d %d %d", &a, &b, &x, &y);
|                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp:96:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
96 |       ll a, b, x, y;scanf("%d %d %d %d", &a, &b, &x, &y);
|                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
```

#### 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 5 ms 3660 KB
00-sample-01 2 ms 3512 KB
10-random_small-00 133 ms 3544 KB
10-random_small-01 12 ms 3528 KB
10-random_small-02 133 ms 4196 KB
10-random_small-03 22 ms 3860 KB
10-random_small-04 222 ms 4120 KB
10-random_small-05 1582 ms 10300 KB
10-random_small-06 32 ms 4292 KB
10-random_small-07 173 ms 6304 KB
10-random_small-08 133 ms 30032 KB
20-random_large-00 5526 ms 421684 KB
20-random_large-01 5526 ms 421628 KB
20-random_large-02 5526 ms 421800 KB
20-random_large-03 5526 ms 421808 KB
20-random_large-04 5526 ms 421692 KB
30-max_query-00 5526 ms 421704 KB
30-max_query-01 5526 ms 421684 KB
30-max_query-02 5526 ms 421696 KB