test/aoj/2842.BIT_2D.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 11:34:20+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/challenges/sources/VPC/HUPC/2842

Depends on

• Binary-Indexed-Tree(2次元) (src/DataStructure/BinaryIndexedTree_2D.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/VPC/HUPC/2842
// competitive-verifier: TLE 1
// competitive-verifier: MLE 128
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include "src/DataStructure/BinaryIndexedTree_2D.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int H, W, T, Q;
 cin >> H >> W >> T >> Q;
 vector<array<int, 6>> query;
 while (Q--) {
  int t, c, h1, w1, h2, w2;
  cin >> t >> c >> h1 >> w1;
  if (c == 2) cin >> h2 >> w2;
  query.push_back({t, c, h1, w1, h2, w2});
  if (c == 0) query.push_back({t + T, -1, h1, w1, h2, w2});
 }
 sort(query.begin(), query.end());
 BinaryIndexedTree_2D<long long> bit1(H, W), bit2(H, W);
 for (auto [t, c, h1, w1, h2, w2]: query) {
  if (c == 0) {
   if (!bit1.sum(h1 - 1, w1 - 1, h1, w1)) bit1.add(h1, w1, 1);
  } else if (c == 1) {
   if (bit2.sum(h1 - 1, w1 - 1, h1, w1)) bit2.add(h1, w1, -1);
  } else if (c == 2) {
   cout << bit2.sum(h1 - 1, w1 - 1, h2, w2) << " " << bit1.sum(h1 - 1, w1 - 1, h2, w2) << '\n';
  } else {
   if (bit1.sum(h1 - 1, w1 - 1, h1, w1)) bit1.add(h1, w1, -1);
   if (!bit2.sum(h1 - 1, w1 - 1, h1, w1)) bit2.add(h1, w1, 1);
  }
 }
}

#line 1 "test/aoj/2842.BIT_2D.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/challenges/sources/VPC/HUPC/2842
// competitive-verifier: TLE 1
// competitive-verifier: MLE 128
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#line 3 "src/DataStructure/BinaryIndexedTree_2D.hpp"
template <typename T> struct BinaryIndexedTree_2D {
 const int h, w;
 std::vector<T> dat;
 BinaryIndexedTree_2D(int H, int W): h(H + 1), w(W + 1), dat(h * w, T()) {}
 void add(int y, int x, T v) {
  for (int i= y; i < h; i+= i & -i)
   for (int j= x, I= i * w; j < w; j+= j & -j) dat[I + j]+= v;
 }
 T sum(int y, int x) const {  // sum (0,y] * (0,x]
  T ret= 0;
  for (int i= y; i; i-= i & -i)
   for (int j= x, I= i * w; j; j-= j & -j) ret+= dat[I + j];
  return ret;
 }
 T sum(int sy, int sx, int ty, int tx) const {  // sum (sy,ty] * (sx,tx]
  return sum(ty, tx) - sum(ty, sx) - sum(sy, tx) + sum(sy, sx);
 }
};
#line 9 "test/aoj/2842.BIT_2D.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int H, W, T, Q;
 cin >> H >> W >> T >> Q;
 vector<array<int, 6>> query;
 while (Q--) {
  int t, c, h1, w1, h2, w2;
  cin >> t >> c >> h1 >> w1;
  if (c == 2) cin >> h2 >> w2;
  query.push_back({t, c, h1, w1, h2, w2});
  if (c == 0) query.push_back({t + T, -1, h1, w1, h2, w2});
 }
 sort(query.begin(), query.end());
 BinaryIndexedTree_2D<long long> bit1(H, W), bit2(H, W);
 for (auto [t, c, h1, w1, h2, w2]: query) {
  if (c == 0) {
   if (!bit1.sum(h1 - 1, w1 - 1, h1, w1)) bit1.add(h1, w1, 1);
  } else if (c == 1) {
   if (bit2.sum(h1 - 1, w1 - 1, h1, w1)) bit2.add(h1, w1, -1);
  } else if (c == 2) {
   cout << bit2.sum(h1 - 1, w1 - 1, h2, w2) << " " << bit1.sum(h1 - 1, w1 - 1, h2, w2) << '\n';
  } else {
   if (bit1.sum(h1 - 1, w1 - 1, h1, w1)) bit1.add(h1, w1, -1);
   if (!bit2.sum(h1 - 1, w1 - 1, h1, w1)) bit2.add(h1, w1, 1);
  }
 }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample_00.in	AC	8 ms	4 MB
g++-13	10_small_rand_00.in	AC	7 ms	4 MB
g++-13	11_middle_rand_00.in	AC	7 ms	4 MB
g++-13	12_large_rand_00.in	AC	10 ms	7 MB
g++-13	13_max_rand_00.in	AC	133 ms	69 MB
g++-13	14_spanshort_rand_00.in	AC	131 ms	71 MB
g++-13	20_small_addonly_00.in	AC	8 ms	3 MB
g++-13	21_middle_addonly_00.in	AC	8 ms	4 MB
g++-13	22_large_addonly_00.in	AC	31 ms	11 MB
g++-13	23_max_addonly_00.in	AC	164 ms	71 MB
g++-13	24_spanshort_addonly_00.in	AC	157 ms	71 MB
g++-13	30_small_eatonly_00.in	AC	8 ms	4 MB
g++-13	31_middle_eatonly_00.in	AC	6 ms	4 MB
g++-13	32_large_eatonly_00.in	AC	26 ms	18 MB
g++-13	33_max_eatonly_00.in	AC	65 ms	68 MB
g++-13	34_spanshort_eatonly_00.in	AC	64 ms	69 MB
g++-13	40_small_queonly_00.in	AC	8 ms	4 MB
g++-13	41_middle_queonly_00.in	AC	8 ms	4 MB
g++-13	42_large_queonly_00.in	AC	50 ms	26 MB
g++-13	43_max_queonly_00.in	AC	150 ms	69 MB
g++-13	44_spanshort_queonly_00.in	AC	157 ms	69 MB
g++-13	50_small_noadd_00.in	AC	8 ms	4 MB
g++-13	51_middle_noadd_00.in	AC	8 ms	4 MB
g++-13	52_large_noadd_00.in	AC	15 ms	5 MB
g++-13	53_max_noadd_00.in	AC	109 ms	69 MB
g++-13	54_spanshort_noadd_00.in	AC	111 ms	69 MB
g++-13	60_small_noeat_00.in	AC	8 ms	4 MB
g++-13	61_middle_noeat_00.in	AC	8 ms	4 MB
g++-13	62_large_noeat_00.in	AC	33 ms	48 MB
g++-13	63_max_noeat_00.in	AC	164 ms	71 MB
g++-13	64_spanshort_noeat_00.in	AC	160 ms	71 MB
g++-13	70_small_noque_00.in	AC	8 ms	4 MB
g++-13	71_middle_noque_00.in	AC	7 ms	4 MB
g++-13	72_large_noque_00.in	AC	17 ms	13 MB
g++-13	73_max_noque_00.in	AC	120 ms	71 MB
g++-13	74_spanshort_noque_00.in	AC	114 ms	71 MB
g++-13	80_small_flrange_00.in	AC	8 ms	4 MB
g++-13	81_middle_flrange_00.in	AC	8 ms	4 MB
g++-13	82_large_flrange_00.in	AC	17 ms	55 MB
g++-13	83_max_flrange_00.in	AC	104 ms	71 MB
g++-13	84_spanshort_flrange_00.in	AC	98 ms	71 MB
g++-13	90_challenge_00.in	AC	62 ms	69 MB
g++-13	90_challenge_01.in	AC	61 ms	69 MB
g++-13	90_challenge_02.in	AC	60 ms	68 MB
clang++-18	00_sample_00.in	AC	7 ms	4 MB
clang++-18	10_small_rand_00.in	AC	6 ms	4 MB
clang++-18	11_middle_rand_00.in	AC	7 ms	4 MB
clang++-18	12_large_rand_00.in	AC	10 ms	7 MB
clang++-18	13_max_rand_00.in	AC	127 ms	71 MB
clang++-18	14_spanshort_rand_00.in	AC	124 ms	71 MB
clang++-18	20_small_addonly_00.in	AC	8 ms	4 MB
clang++-18	21_middle_addonly_00.in	AC	7 ms	4 MB
clang++-18	22_large_addonly_00.in	AC	29 ms	11 MB
clang++-18	23_max_addonly_00.in	AC	157 ms	71 MB
clang++-18	24_spanshort_addonly_00.in	AC	152 ms	71 MB
clang++-18	30_small_eatonly_00.in	AC	8 ms	4 MB
clang++-18	31_middle_eatonly_00.in	AC	7 ms	4 MB
clang++-18	32_large_eatonly_00.in	AC	25 ms	18 MB
clang++-18	33_max_eatonly_00.in	AC	62 ms	68 MB
clang++-18	34_spanshort_eatonly_00.in	AC	62 ms	69 MB
clang++-18	40_small_queonly_00.in	AC	8 ms	4 MB
clang++-18	41_middle_queonly_00.in	AC	8 ms	4 MB
clang++-18	42_large_queonly_00.in	AC	49 ms	26 MB
clang++-18	43_max_queonly_00.in	AC	147 ms	69 MB
clang++-18	44_spanshort_queonly_00.in	AC	149 ms	69 MB
clang++-18	50_small_noadd_00.in	AC	8 ms	4 MB
clang++-18	51_middle_noadd_00.in	AC	7 ms	4 MB
clang++-18	52_large_noadd_00.in	AC	15 ms	5 MB
clang++-18	53_max_noadd_00.in	AC	106 ms	69 MB
clang++-18	54_spanshort_noadd_00.in	AC	111 ms	69 MB
clang++-18	60_small_noeat_00.in	AC	9 ms	4 MB
clang++-18	61_middle_noeat_00.in	AC	7 ms	4 MB
clang++-18	62_large_noeat_00.in	AC	33 ms	48 MB
clang++-18	63_max_noeat_00.in	AC	156 ms	71 MB
clang++-18	64_spanshort_noeat_00.in	AC	146 ms	71 MB
clang++-18	70_small_noque_00.in	AC	8 ms	3 MB
clang++-18	71_middle_noque_00.in	AC	6 ms	4 MB
clang++-18	72_large_noque_00.in	AC	17 ms	13 MB
clang++-18	73_max_noque_00.in	AC	112 ms	71 MB
clang++-18	74_spanshort_noque_00.in	AC	105 ms	71 MB
clang++-18	80_small_flrange_00.in	AC	8 ms	4 MB
clang++-18	81_middle_flrange_00.in	AC	6 ms	4 MB
clang++-18	82_large_flrange_00.in	AC	15 ms	55 MB
clang++-18	83_max_flrange_00.in	AC	94 ms	69 MB
clang++-18	84_spanshort_flrange_00.in	AC	88 ms	69 MB
clang++-18	90_challenge_00.in	AC	58 ms	68 MB
clang++-18	90_challenge_01.in	AC	56 ms	68 MB
clang++-18	90_challenge_02.in	AC	57 ms	68 MB

Back to top page