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
Task C - 宝探し 2
User tonegawa
Language C++ (GCC 9.2.1)
Score 0
Code Size 2941 Byte
Status
Exec Time 5526 ms
Memory 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