oj.uz

Submission #561900

# Submission time Handle Problem Language Result Execution time Memory
561900 2022-05-13T17:56:07 Z hoanghq2004 Rectangles (IOI19_rect) C++14
100 / 100
 4603 ms 865564 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "rect.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2510;

int up[N][N], down[N][N], lft[N][N], rgt[N][N];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
vector <int> toX[N], toY[N][N];

int BIT[N];
inline void add(int i, int d) {
    ++i;
    for (; i < N; i += i & - i) BIT[i] += d;
}

inline int get(int i) {
    int ans = 0;
    ++i;
    for (; i; i -= i & - i) ans += BIT[i];
    return ans;
}

int tmp_max[N], tmp_min[N];

struct SegmentTree {
    int mini[N * 4], maxi[N * 4];
    inline void build(int id, int L, int R) {
        if (L == R) {
            mini[id] = tmp_min[L];
            maxi[id] = tmp_max[L];
            return;
        }
        int mid = L + R >> 1;
        build(id * 2, L, mid);
        build(id * 2 + 1, mid + 1, R);
        mini[id] = min(mini[id * 2], mini[id * 2 + 1]);
        maxi[id] = max(maxi[id * 2], maxi[id * 2 + 1]);
    }
    inline int get_min(int id, int L, int R, int u, int v) {
        if (u > R || L > v) return 1e9;
        if (u <= L && R <= v) return mini[id];
        int mid = L + R >> 1;
        return min(get_min(id * 2, L, mid, u, v), get_min(id * 2 + 1, mid + 1, R, u, v));
    }
    inline int get_rgt(int id, int L, int R, int i, int k) {
        if (i > R || maxi[id] <= k) return -1;
        if (L == R) return L;
        int mid = L + R >> 1;
        int ans = get_rgt(id * 2, L, mid, i, k);
        if (ans == -1) ans = get_rgt(id * 2 + 1, mid + 1, R, i, k);
        return ans;
    }
} X[N], Y[N];

long long count_rectangles(vector <vector <int>> a) {
    int n = a.size();
    int m = a[0].size();
    for (int i = 0; i < n; ++i) {
        stack <int> stk;
        for (int j = 0; j < m; ++j) {
            while (stk.size() && a[i][j] >= a[i][stk.top()]) {
                rgt[i][stk.top()] = j - 1;
                stk.pop();
            }
            stk.push(j);
        }
        while (stk.size()) {
            rgt[i][stk.top()] = m - 1;
            stk.pop();
        }
        for (int j = m - 1; j >= 0; --j) {
            while (stk.size() && a[i][j] >= a[i][stk.top()]) {
                lft[i][stk.top()] = j + 1;
                stk.pop();
            }
            stk.push(j);
        }
        while (stk.size()) {
            lft[i][stk.top()] = 0;
            stk.pop();
        }
    }
    for (int i = 0; i < m; ++i) {
        stack <int> stk;
        for (int j = 0; j < n; ++j) {
            while (stk.size() && a[j][i] >= a[stk.top()][i]) {
                down[stk.top()][i] = j - 1;
                stk.pop();
            }
            stk.push(j);
        }
        while (stk.size()) {
            down[stk.top()][i] = n - 1;
            stk.pop();
        }
        for (int j = n - 1; j >= 0; --j) {
            while (stk.size() && a[j][i] >= a[stk.top()][i]) {
                up[stk.top()][i] = j + 1;
                stk.pop();
            }
            stk.push(j);
        }
        while (stk.size()) {
            up[stk.top()][i] = 0;
            stk.pop();
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {

            if (down[i][j] < n - 1 && down[i][j] >= i + 1) {
                toY[i + 1][j].push_back(down[i][j]);
            }
            if (up[i][j] > 0 && a[i][j] != a[up[i][j] - 1][j] && up[i][j] <= i - 1) {
                toY[up[i][j]][j].push_back(i - 1);
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) tmp_min[j] = down[i][j], tmp_max[j] = up[i][j];
        Y[i].build(1, 0, m - 1);
    }
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) tmp_min[j] = rgt[j][i], tmp_max[j] = lft[j][i];
        X[i].build(1, 0, n - 1);
    }
    long long ans = 0;
    for (int u = 1; u < n - 1; ++u) {
        for (int v = 0; v < m; ++v) toX[v].clear();
        for (int v = 0; v < m; ++v) {
            if (rgt[u][v] < m - 1 && rgt[u][v] >= v + 1) {
                toX[v + 1].push_back(rgt[u][v]);
            }
            if (lft[u][v] > 0 && a[u][v] != a[u][lft[u][v] - 1] && lft[u][v] <= v - 1) {
                toX[lft[u][v]].push_back(v - 1);
            }
        }
        for (int v = 1; v < m - 1; ++v) {
            if (toX[v].empty() || toY[u][v].empty()) continue;
            vector <tuple <int, int, int> > events;
            for (auto w: toY[u][v]) { // (w, v)
                int ww = Y[w + 1].get_rgt(1, 0, m - 1, v, u);
                if (ww == -1) ww = m; --ww;
                ww = min(ww, X[v - 1].get_min(1, 0, n - 1, u, w));
                ww = min(ww, m - 2);
                add(w, 1);
                events.push_back({ww, 1, w});
            }
            for (auto w: toX[v]) { // (u, w)
                int ww = X[w + 1].get_rgt(1, 0, n - 1, u, v);
                if (ww == -1) ww = n; --ww;
                ww = min(ww, Y[u - 1].get_min(1, 0, m - 1, v, w));
                ww = min(ww, n - 2);
                events.push_back({w, 0, ww});
            }
            sort(events.begin(), events.end());
            for (auto [_, sign, k]: events) {
                if (sign == 0) ans += get(k);
                else if (sign == -1) add(k, 1);
                else add(k, -1);
            }
        }
    }
    return ans;
}

//int main() {
//    freopen("IOI19_rect.inp", "r", stdin);
////    freopen("IOI19_rect.out", "w", stdout);
//	int n, m;
//    cin >> n >> m;
//	vector<vector<int>> a(n, vector<int>(m));
//	for (int i = 0; i < n; i++)	{
//		for (int j = 0; j < m; j++) {
//            cin >> a[i][j];
//		}
//	}
//	cout << count_rectangles(a) << '\n';
//}

Compilation message

rect.cpp: In member function 'void SegmentTree::build(int, int, int)':
rect.cpp:44:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         int mid = L + R >> 1;
      |                   ~~^~~
rect.cpp: In member function 'int SegmentTree::get_min(int, int, int, int, int)':
rect.cpp:53:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         int mid = L + R >> 1;
      |                   ~~^~~
rect.cpp: In member function 'int SegmentTree::get_rgt(int, int, int, int, int)':
rect.cpp:59:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         int mid = L + R >> 1;
      |                   ~~^~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:154:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  154 |                 if (ww == -1) ww = m; --ww;
      |                 ^~
rect.cpp:154:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  154 |                 if (ww == -1) ww = m; --ww;
      |                                       ^~
rect.cpp:162:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  162 |                 if (ww == -1) ww = n; --ww;
      |                 ^~
rect.cpp:162:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  162 |                 if (ww == -1) ww = n; --ww;
      |                                       ^~
rect.cpp:168:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  168 |             for (auto [_, sign, k]: events) {
      |                       ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 148512 KB Output is correct
2 Correct 69 ms 149360 KB Output is correct
3 Correct 71 ms 149336 KB Output is correct
4 Correct 68 ms 149300 KB Output is correct
5 Correct 69 ms 149236 KB Output is correct
6 Correct 74 ms 149328 KB Output is correct
7 Correct 79 ms 149164 KB Output is correct
8 Correct 70 ms 148872 KB Output is correct
9 Correct 76 ms 149356 KB Output is correct
10 Correct 68 ms 149340 KB Output is correct
11 Correct 78 ms 149324 KB Output is correct
12 Correct 69 ms 149324 KB Output is correct
13 Correct 73 ms 148300 KB Output is correct
14 Correct 82 ms 148508 KB Output is correct
15 Correct 69 ms 148576 KB Output is correct
16 Correct 72 ms 148300 KB Output is correct
17 Correct 69 ms 148252 KB Output is correct
18 Correct 73 ms 148336 KB Output is correct
19 Correct 82 ms 149268 KB Output is correct
20 Correct 71 ms 149196 KB Output is correct
21 Correct 69 ms 148484 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 148512 KB Output is correct
2 Correct 69 ms 149360 KB Output is correct
3 Correct 71 ms 149336 KB Output is correct
4 Correct 68 ms 149300 KB Output is correct
5 Correct 69 ms 149236 KB Output is correct
6 Correct 74 ms 149328 KB Output is correct
7 Correct 79 ms 149164 KB Output is correct
8 Correct 70 ms 148872 KB Output is correct
9 Correct 76 ms 149356 KB Output is correct
10 Correct 68 ms 149340 KB Output is correct
11 Correct 78 ms 149324 KB Output is correct
12 Correct 69 ms 149324 KB Output is correct
13 Correct 73 ms 148300 KB Output is correct
14 Correct 82 ms 148508 KB Output is correct
15 Correct 69 ms 148576 KB Output is correct
16 Correct 72 ms 148300 KB Output is correct
17 Correct 69 ms 148252 KB Output is correct
18 Correct 73 ms 148336 KB Output is correct
19 Correct 82 ms 149268 KB Output is correct
20 Correct 71 ms 149196 KB Output is correct
21 Correct 69 ms 148484 KB Output is correct
22 Correct 70 ms 151500 KB Output is correct
23 Correct 84 ms 151508 KB Output is correct
24 Correct 77 ms 151492 KB Output is correct
25 Correct 71 ms 151500 KB Output is correct
26 Correct 74 ms 151320 KB Output is correct
27 Correct 81 ms 151444 KB Output is correct
28 Correct 87 ms 151420 KB Output is correct
29 Correct 77 ms 150732 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 148512 KB Output is correct
2 Correct 69 ms 149360 KB Output is correct
3 Correct 71 ms 149336 KB Output is correct
4 Correct 68 ms 149300 KB Output is correct
5 Correct 69 ms 149236 KB Output is correct
6 Correct 74 ms 149328 KB Output is correct
7 Correct 79 ms 149164 KB Output is correct
8 Correct 70 ms 148872 KB Output is correct
9 Correct 76 ms 149356 KB Output is correct
10 Correct 68 ms 149340 KB Output is correct
11 Correct 78 ms 149324 KB Output is correct
12 Correct 69 ms 149324 KB Output is correct
13 Correct 73 ms 148300 KB Output is correct
14 Correct 82 ms 148508 KB Output is correct
15 Correct 69 ms 148576 KB Output is correct
16 Correct 72 ms 148300 KB Output is correct
17 Correct 70 ms 151500 KB Output is correct
18 Correct 84 ms 151508 KB Output is correct
19 Correct 77 ms 151492 KB Output is correct
20 Correct 71 ms 151500 KB Output is correct
21 Correct 74 ms 151320 KB Output is correct
22 Correct 81 ms 151444 KB Output is correct
23 Correct 87 ms 151420 KB Output is correct
24 Correct 77 ms 150732 KB Output is correct
25 Correct 69 ms 148252 KB Output is correct
26 Correct 73 ms 148336 KB Output is correct
27 Correct 82 ms 149268 KB Output is correct
28 Correct 71 ms 149196 KB Output is correct
29 Correct 69 ms 148484 KB Output is correct
30 Correct 86 ms 158540 KB Output is correct
31 Correct 87 ms 158480 KB Output is correct
32 Correct 110 ms 158540 KB Output is correct
33 Correct 94 ms 157656 KB Output is correct
34 Correct 92 ms 157960 KB Output is correct
35 Correct 92 ms 157984 KB Output is correct
36 Correct 92 ms 157836 KB Output is correct
37 Correct 97 ms 157764 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 148512 KB Output is correct
2 Correct 69 ms 149360 KB Output is correct
3 Correct 71 ms 149336 KB Output is correct
4 Correct 68 ms 149300 KB Output is correct
5 Correct 69 ms 149236 KB Output is correct
6 Correct 74 ms 149328 KB Output is correct
7 Correct 79 ms 149164 KB Output is correct
8 Correct 70 ms 148872 KB Output is correct
9 Correct 76 ms 149356 KB Output is correct
10 Correct 68 ms 149340 KB Output is correct
11 Correct 78 ms 149324 KB Output is correct
12 Correct 69 ms 149324 KB Output is correct
13 Correct 73 ms 148300 KB Output is correct
14 Correct 82 ms 148508 KB Output is correct
15 Correct 69 ms 148576 KB Output is correct
16 Correct 72 ms 148300 KB Output is correct
17 Correct 70 ms 151500 KB Output is correct
18 Correct 84 ms 151508 KB Output is correct
19 Correct 77 ms 151492 KB Output is correct
20 Correct 71 ms 151500 KB Output is correct
21 Correct 74 ms 151320 KB Output is correct
22 Correct 81 ms 151444 KB Output is correct
23 Correct 87 ms 151420 KB Output is correct
24 Correct 77 ms 150732 KB Output is correct
25 Correct 86 ms 158540 KB Output is correct
26 Correct 87 ms 158480 KB Output is correct
27 Correct 110 ms 158540 KB Output is correct
28 Correct 94 ms 157656 KB Output is correct
29 Correct 92 ms 157960 KB Output is correct
30 Correct 92 ms 157984 KB Output is correct
31 Correct 92 ms 157836 KB Output is correct
32 Correct 97 ms 157764 KB Output is correct
33 Correct 69 ms 148252 KB Output is correct
34 Correct 73 ms 148336 KB Output is correct
35 Correct 82 ms 149268 KB Output is correct
36 Correct 71 ms 149196 KB Output is correct
37 Correct 69 ms 148484 KB Output is correct
38 Correct 141 ms 212464 KB Output is correct
39 Correct 185 ms 213956 KB Output is correct
40 Correct 181 ms 206432 KB Output is correct
41 Correct 237 ms 207592 KB Output is correct
42 Correct 314 ms 220116 KB Output is correct
43 Correct 345 ms 220132 KB Output is correct
44 Correct 308 ms 220056 KB Output is correct
45 Correct 307 ms 216592 KB Output is correct
46 Correct 178 ms 208672 KB Output is correct
47 Correct 212 ms 210020 KB Output is correct
48 Correct 384 ms 212736 KB Output is correct
49 Correct 360 ms 212644 KB Output is correct
50 Correct 219 ms 189004 KB Output is correct
51 Correct 213 ms 183392 KB Output is correct
52 Correct 331 ms 212172 KB Output is correct
53 Correct 327 ms 212092 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 169164 KB Output is correct
2 Correct 87 ms 166148 KB Output is correct
3 Correct 79 ms 169148 KB Output is correct
4 Correct 73 ms 148356 KB Output is correct
5 Correct 79 ms 169128 KB Output is correct
6 Correct 80 ms 169164 KB Output is correct
7 Correct 77 ms 169116 KB Output is correct
8 Correct 78 ms 169132 KB Output is correct
9 Correct 80 ms 169156 KB Output is correct
10 Correct 87 ms 168952 KB Output is correct
11 Correct 77 ms 168912 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 148252 KB Output is correct
2 Correct 73 ms 148336 KB Output is correct
3 Correct 82 ms 149268 KB Output is correct
4 Correct 71 ms 149196 KB Output is correct
5 Correct 69 ms 148484 KB Output is correct
6 Correct 71 ms 148604 KB Output is correct
7 Correct 758 ms 423484 KB Output is correct
8 Correct 1648 ms 702920 KB Output is correct
9 Correct 1727 ms 704792 KB Output is correct
10 Correct 1708 ms 704760 KB Output is correct
11 Correct 420 ms 409952 KB Output is correct
12 Correct 755 ms 641740 KB Output is correct
13 Correct 779 ms 655860 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 148512 KB Output is correct
2 Correct 69 ms 149360 KB Output is correct
3 Correct 71 ms 149336 KB Output is correct
4 Correct 68 ms 149300 KB Output is correct
5 Correct 69 ms 149236 KB Output is correct
6 Correct 74 ms 149328 KB Output is correct
7 Correct 79 ms 149164 KB Output is correct
8 Correct 70 ms 148872 KB Output is correct
9 Correct 76 ms 149356 KB Output is correct
10 Correct 68 ms 149340 KB Output is correct
11 Correct 78 ms 149324 KB Output is correct
12 Correct 69 ms 149324 KB Output is correct
13 Correct 73 ms 148300 KB Output is correct
14 Correct 82 ms 148508 KB Output is correct
15 Correct 69 ms 148576 KB Output is correct
16 Correct 72 ms 148300 KB Output is correct
17 Correct 70 ms 151500 KB Output is correct
18 Correct 84 ms 151508 KB Output is correct
19 Correct 77 ms 151492 KB Output is correct
20 Correct 71 ms 151500 KB Output is correct
21 Correct 74 ms 151320 KB Output is correct
22 Correct 81 ms 151444 KB Output is correct
23 Correct 87 ms 151420 KB Output is correct
24 Correct 77 ms 150732 KB Output is correct
25 Correct 86 ms 158540 KB Output is correct
26 Correct 87 ms 158480 KB Output is correct
27 Correct 110 ms 158540 KB Output is correct
28 Correct 94 ms 157656 KB Output is correct
29 Correct 92 ms 157960 KB Output is correct
30 Correct 92 ms 157984 KB Output is correct
31 Correct 92 ms 157836 KB Output is correct
32 Correct 97 ms 157764 KB Output is correct
33 Correct 141 ms 212464 KB Output is correct
34 Correct 185 ms 213956 KB Output is correct
35 Correct 181 ms 206432 KB Output is correct
36 Correct 237 ms 207592 KB Output is correct
37 Correct 314 ms 220116 KB Output is correct
38 Correct 345 ms 220132 KB Output is correct
39 Correct 308 ms 220056 KB Output is correct
40 Correct 307 ms 216592 KB Output is correct
41 Correct 178 ms 208672 KB Output is correct
42 Correct 212 ms 210020 KB Output is correct
43 Correct 384 ms 212736 KB Output is correct
44 Correct 360 ms 212644 KB Output is correct
45 Correct 219 ms 189004 KB Output is correct
46 Correct 213 ms 183392 KB Output is correct
47 Correct 331 ms 212172 KB Output is correct
48 Correct 327 ms 212092 KB Output is correct
49 Correct 91 ms 169164 KB Output is correct
50 Correct 87 ms 166148 KB Output is correct
51 Correct 79 ms 169148 KB Output is correct
52 Correct 73 ms 148356 KB Output is correct
53 Correct 79 ms 169128 KB Output is correct
54 Correct 80 ms 169164 KB Output is correct
55 Correct 77 ms 169116 KB Output is correct
56 Correct 78 ms 169132 KB Output is correct
57 Correct 80 ms 169156 KB Output is correct
58 Correct 87 ms 168952 KB Output is correct
59 Correct 77 ms 168912 KB Output is correct
60 Correct 71 ms 148604 KB Output is correct
61 Correct 758 ms 423484 KB Output is correct
62 Correct 1648 ms 702920 KB Output is correct
63 Correct 1727 ms 704792 KB Output is correct
64 Correct 1708 ms 704760 KB Output is correct
65 Correct 420 ms 409952 KB Output is correct
66 Correct 755 ms 641740 KB Output is correct
67 Correct 779 ms 655860 KB Output is correct
68 Correct 69 ms 148252 KB Output is correct
69 Correct 73 ms 148336 KB Output is correct
70 Correct 82 ms 149268 KB Output is correct
71 Correct 71 ms 149196 KB Output is correct
72 Correct 69 ms 148484 KB Output is correct
73 Correct 1096 ms 753700 KB Output is correct
74 Correct 1752 ms 771864 KB Output is correct
75 Correct 1799 ms 672964 KB Output is correct
76 Correct 2678 ms 690824 KB Output is correct
77 Correct 4139 ms 851404 KB Output is correct
78 Correct 2435 ms 505812 KB Output is correct
79 Correct 2457 ms 555628 KB Output is correct
80 Correct 4446 ms 756772 KB Output is correct
81 Correct 2606 ms 514068 KB Output is correct
82 Correct 3435 ms 622236 KB Output is correct
83 Correct 4603 ms 771872 KB Output is correct
84 Correct 2260 ms 522844 KB Output is correct
85 Correct 4034 ms 764540 KB Output is correct
86 Correct 3985 ms 752248 KB Output is correct
87 Correct 2326 ms 609864 KB Output is correct
88 Correct 3862 ms 865204 KB Output is correct
89 Correct 3861 ms 865552 KB Output is correct
90 Correct 3536 ms 865564 KB Output is correct