This documentation is automatically generated by competitive-verifier/competitive-verifier
#include "../2DBIT.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DSL_5_B
template <class T, class U>
inline bool chmax(T &a, U b) {
if (a < b) {
a = b;
return true;
}
return false;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
const int n = 1001;
BIT2D<int> bit(n, n);
int q;
cin >> q;
while (q--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
a++, b++, c++, d++;
//(a,c],(b,d]
bit.add(c, d, 1);
bit.add(a, d, -1);
bit.add(c, b, -1);
bit.add(a, b, 1);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
chmax(ans, bit.sum(i, j));
}
}
cout << ans << endl;
}
#line 1 "2DBIT.cpp"
#include <bits/stdc++.h>
using namespace std;
template <class T>
struct BIT2D {
int n, m;
vector<vector<T>> bit;
BIT2D(int n, int m) : n(n), m(m) { bit.resize(n + 1, vector<T>(m + 1)); }
void add(int a, int b, T w) {
for (int x = a; x <= n; x += x & -x) {
for (int y = b; y <= m; y += y & -y) {
bit[x][y] += w;
}
}
}
T sum(int a, int b) {
T res = 0;
for (int x = a; x > 0; x -= x & -x) {
for (int y = b; y > 0; y -= y & -y) {
res += bit[x][y];
}
}
return res;
}
T sum(int a, int b, int c, int d) {
//[a,c],[b,d]
return sum(c, d) - sum(a - 1, d) - sum(c, b - 1) + sum(a - 1, b - 1);
}
};
#line 2 "test/2DBIT.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/DSL_5_B
template <class T, class U>
inline bool chmax(T &a, U b) {
if (a < b) {
a = b;
return true;
}
return false;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
const int n = 1001;
BIT2D<int> bit(n, n);
int q;
cin >> q;
while (q--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
a++, b++, c++, d++;
//(a,c],(b,d]
bit.add(c, d, 1);
bit.add(a, d, -1);
bit.add(c, b, -1);
bit.add(a, b, 1);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
chmax(ans, bit.sum(i, j));
}
}
cout << ans << endl;
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | 00_sample_00.in |
![]() |
19 ms | 7 MB |
g++ | 00_sample_01.in |
![]() |
19 ms | 7 MB |
g++ | 00_sample_02.in |
![]() |
19 ms | 7 MB |
g++ | 01_small_00.in |
![]() |
20 ms | 7 MB |
g++ | 01_small_01.in |
![]() |
19 ms | 7 MB |
g++ | 01_small_02.in |
![]() |
20 ms | 7 MB |
g++ | 02_minimum_00.in |
![]() |
20 ms | 7 MB |
g++ | 02_minimum_01.in |
![]() |
19 ms | 7 MB |
g++ | 02_minimum_02.in |
![]() |
19 ms | 7 MB |
g++ | 02_minimum_03.in |
![]() |
19 ms | 7 MB |
g++ | 03_rand_00.in |
![]() |
19 ms | 7 MB |
g++ | 03_rand_01.in |
![]() |
19 ms | 7 MB |
g++ | 03_rand_02.in |
![]() |
20 ms | 7 MB |
g++ | 03_rand_03.in |
![]() |
20 ms | 7 MB |
g++ | 04_medium_00.in |
![]() |
20 ms | 7 MB |
g++ | 04_medium_01.in |
![]() |
19 ms | 7 MB |
g++ | 04_medium_02.in |
![]() |
19 ms | 7 MB |
g++ | 04_medium_03.in |
![]() |
19 ms | 7 MB |
g++ | 05_large_00.in |
![]() |
19 ms | 7 MB |
g++ | 05_large_01.in |
![]() |
19 ms | 7 MB |
g++ | 05_large_02.in |
![]() |
20 ms | 7 MB |
g++ | 05_large_03.in |
![]() |
20 ms | 7 MB |
g++ | 06_corner_00.in |
![]() |
26 ms | 7 MB |
g++ | 06_corner_01.in |
![]() |
26 ms | 7 MB |
g++ | 06_corner_02.in |
![]() |
28 ms | 7 MB |
g++ | 06_corner_03.in |
![]() |
33 ms | 7 MB |
g++ | 06_corner_04.in |
![]() |
29 ms | 7 MB |
g++ | 07_corner_fit_00.in |
![]() |
45 ms | 7 MB |
g++ | 07_corner_fit_01.in |
![]() |
50 ms | 7 MB |
g++ | 08_overlaped_00.in |
![]() |
47 ms | 7 MB |
clang++ | 00_sample_00.in |
![]() |
20 ms | 7 MB |
clang++ | 00_sample_01.in |
![]() |
20 ms | 7 MB |
clang++ | 00_sample_02.in |
![]() |
20 ms | 7 MB |
clang++ | 01_small_00.in |
![]() |
19 ms | 7 MB |
clang++ | 01_small_01.in |
![]() |
19 ms | 7 MB |
clang++ | 01_small_02.in |
![]() |
19 ms | 7 MB |
clang++ | 02_minimum_00.in |
![]() |
19 ms | 7 MB |
clang++ | 02_minimum_01.in |
![]() |
20 ms | 7 MB |
clang++ | 02_minimum_02.in |
![]() |
20 ms | 7 MB |
clang++ | 02_minimum_03.in |
![]() |
19 ms | 7 MB |
clang++ | 03_rand_00.in |
![]() |
20 ms | 7 MB |
clang++ | 03_rand_01.in |
![]() |
19 ms | 7 MB |
clang++ | 03_rand_02.in |
![]() |
19 ms | 7 MB |
clang++ | 03_rand_03.in |
![]() |
19 ms | 7 MB |
clang++ | 04_medium_00.in |
![]() |
19 ms | 7 MB |
clang++ | 04_medium_01.in |
![]() |
19 ms | 7 MB |
clang++ | 04_medium_02.in |
![]() |
19 ms | 7 MB |
clang++ | 04_medium_03.in |
![]() |
19 ms | 7 MB |
clang++ | 05_large_00.in |
![]() |
19 ms | 7 MB |
clang++ | 05_large_01.in |
![]() |
20 ms | 7 MB |
clang++ | 05_large_02.in |
![]() |
20 ms | 7 MB |
clang++ | 05_large_03.in |
![]() |
20 ms | 7 MB |
clang++ | 06_corner_00.in |
![]() |
26 ms | 7 MB |
clang++ | 06_corner_01.in |
![]() |
27 ms | 7 MB |
clang++ | 06_corner_02.in |
![]() |
26 ms | 7 MB |
clang++ | 06_corner_03.in |
![]() |
33 ms | 7 MB |
clang++ | 06_corner_04.in |
![]() |
29 ms | 7 MB |
clang++ | 07_corner_fit_00.in |
![]() |
44 ms | 7 MB |
clang++ | 07_corner_fit_01.in |
![]() |
48 ms | 7 MB |
clang++ | 08_overlaped_00.in |
![]() |
48 ms | 7 MB |