oj.uz

답안 #820869

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
820869 2023-08-11T06:20:31 Z resting Rectangles (IOI19_rect) C++17
100 / 100
 3796 ms 782000 KB 
//#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

struct dsu {
    vector<int> p, s, l, r;
    dsu(int n) : p(n, -1), s(n, 0), l(n), r(n) { for (int i = 0; i < n; i++)  l[i] = r[i] = i; };
    dsu() :dsu(0) {};
    int getp(int v) {
        return p[v] == -1 ? v : p[v] = getp(p[v]);
    }
    void merge(int a, int b) {
        a = getp(a); b = getp(b);
        if (a == b) return;
        if (s[a] < s[b]) swap(a, b);
        if (s[a] == s[b]) s[a]++;
        l[a] = min(l[a], l[b]);
        r[a] = max(r[a], r[b]);
        p[b] = a;
    }
};


const int mx = 2505;
//binary index tree
struct bit {
    vector<int> b; int n;
    bit(int n) : n(n), b(n, 0) {}
    void upd(int i, int v) { for (i++; i <= n; i += i & -i) b[i - 1] += v; }
    void upd(int l, int r, int v) { upd(l, v); upd(r + 1, -v); }
    int q(int i) { int v = 0; for (i++; i > 0; i -= i & -i) v += b[i - 1];return v; }
    int q(int l, int r) { return q(r) - q(l - 1); }
} uwu(mx);


long long count_rectangles(vector<vector<int32_t>> a) {
    int n = a.size(), m = a[0].size();
    vector<vector<vector<pair<short, short>>>> vert, hori; // idfc
    vert = hori = vector<vector<vector<pair<short, short>>>>(n, vector<vector<pair<short, short>>>(m));
    for (int i = 0; i < n; i++) {
        vector<pair<int, int>> v;
        vector<int> vis(mx, 0);
        for (int j = 0; j < m; j++) v.push_back(make_pair((int)a[i][j], j));
        dsu ac(mx);
        sort(v.begin(), v.end());
        for (auto& x : v) {
            auto [p, t] = x;
            vis[t] = 1;
            if (t && vis[t - 1]) ac.merge(t - 1, t);
            if (t + 1 < m && vis[t + 1]) ac.merge(t + 1, t);
            t = ac.getp(t);
            if (ac.l[t] && ac.r[t] + 1 < m && a[i][ac.l[t] - 1] > p && a[i][ac.r[t] + 1] > p) {
                hori[i][ac.l[t]].push_back(pair<short, short>(ac.r[t] - ac.l[t] + 1, 1));
            }
        }
    }

    for (int i = 0; i < m; i++) {
        vector<pair<int, int>> v;
        vector<int> vis(mx, 0);
        for (int j = 0; j < n; j++) v.push_back(make_pair((int)a[j][i], j));
        dsu ac(mx);
        sort(v.begin(), v.end());
        for (auto& x : v) {
            auto [p, t] = x;
            vis[t] = 1;
            if (t && vis[t - 1])ac.merge(t - 1, t);
            if (t + 1 < n && vis[t + 1]) ac.merge(t + 1, t);
            t = ac.getp(t);
            if (ac.l[t] && ac.r[t] + 1 < n && a[ac.l[t] - 1][i] > p && a[ac.r[t] + 1][i] > p) {
                vert[ac.l[t]][i].push_back(pair<short, short>(ac.r[t] - ac.l[t] + 1, 1));
            }
        }
    }

    long long res = 0;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            // cout << i << "," << j << endl;
            sort(hori[i][j].begin(), hori[i][j].end());
            sort(vert[i][j].begin(), vert[i][j].end());
            if (i + 1 < n) {
                for (auto& x : hori[i][j]) {
                    auto tmp = lower_bound(hori[i + 1][j].begin(), hori[i + 1][j].end(), make_pair(x.first, (short)0));
                    if (tmp != hori[i + 1][j].end() && tmp->first == x.first)
                        x.second += tmp->second;
                }
            }
            if (j + 1 < m) {
                for (auto& x : vert[i][j]) {
                    auto tmp = lower_bound(vert[i][j + 1].begin(), vert[i][j + 1].end(), make_pair(x.first, (short)0));
                    if (tmp != vert[i][j + 1].end() && tmp->first == x.first)
                        x.second += tmp->second;
                }
            }
            vector<pair<int, int>> bruh;
            for (auto& x : vert[i][j]) bruh.push_back(make_pair((int)x.second, (int)x.first));
            sort(bruh.begin(), bruh.end());
            int cur = 0;

            for (auto& x : hori[i][j]) {
                while (cur < bruh.size() && bruh[cur].first < x.first) {
                    res += uwu.q(bruh[cur].second, mx - 1);
                    cur++;
                }
                uwu.upd(x.second, 1);
            }
            while (cur < bruh.size()) {
                res += uwu.q(bruh[cur].second, mx - 1);
                cur++;
            }
            for (auto& x : hori[i][j]) {
                uwu.upd(x.second, -1);
            }
        }
    }
    return res;
}

// int32_t main() {
//     int a = count_rectangles({ {4, 8, 7, 5, 6},
//         { 7, 4, 10, 3, 5 },
//         { 9, 7, 20, 14, 2 },
//         { 9, 14, 7, 3, 6 },
//         { 5, 7, 5, 2, 7 },
//         {4, 5, 13, 5, 6} });
//     cout << a << endl;
// }

Compilation message

rect.cpp: In constructor 'bit::bit(int)':
rect.cpp:27:24: warning: 'bit::n' will be initialized after [-Wreorder]
   27 |     vector<int> b; int n;
      |                        ^
rect.cpp:27:17: warning:   'std::vector<int> bit::b' [-Wreorder]
   27 |     vector<int> b; int n;
      |                 ^
rect.cpp:28:5: warning:   when initialized here [-Wreorder]
   28 |     bit(int n) : n(n), b(n, 0) {}
      |     ^~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:102:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |                 while (cur < bruh.size() && bruh[cur].first < x.first) {
      |                        ~~~~^~~~~~~~~~~~~
rect.cpp:108:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             while (cur < bruh.size()) {
      |                    ~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 3 ms 1100 KB Output is correct
23 Correct 4 ms 1108 KB Output is correct
24 Correct 3 ms 1108 KB Output is correct
25 Correct 2 ms 852 KB Output is correct
26 Correct 4 ms 880 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 3 ms 852 KB Output is correct
29 Correct 2 ms 596 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 3 ms 1100 KB Output is correct
18 Correct 4 ms 1108 KB Output is correct
19 Correct 3 ms 1108 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 4 ms 880 KB Output is correct
22 Correct 3 ms 852 KB Output is correct
23 Correct 3 ms 852 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 16 ms 4948 KB Output is correct
31 Correct 18 ms 4948 KB Output is correct
32 Correct 16 ms 5064 KB Output is correct
33 Correct 13 ms 3296 KB Output is correct
34 Correct 23 ms 3796 KB Output is correct
35 Correct 19 ms 3764 KB Output is correct
36 Correct 17 ms 3772 KB Output is correct
37 Correct 17 ms 3676 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 3 ms 1100 KB Output is correct
18 Correct 4 ms 1108 KB Output is correct
19 Correct 3 ms 1108 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 4 ms 880 KB Output is correct
22 Correct 3 ms 852 KB Output is correct
23 Correct 3 ms 852 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 16 ms 4948 KB Output is correct
26 Correct 18 ms 4948 KB Output is correct
27 Correct 16 ms 5064 KB Output is correct
28 Correct 13 ms 3296 KB Output is correct
29 Correct 23 ms 3796 KB Output is correct
30 Correct 19 ms 3764 KB Output is correct
31 Correct 17 ms 3772 KB Output is correct
32 Correct 17 ms 3676 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 0 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 0 ms 340 KB Output is correct
38 Correct 139 ms 42540 KB Output is correct
39 Correct 115 ms 36396 KB Output is correct
40 Correct 116 ms 36436 KB Output is correct
41 Correct 87 ms 30084 KB Output is correct
42 Correct 222 ms 57768 KB Output is correct
43 Correct 193 ms 57800 KB Output is correct
44 Correct 210 ms 57892 KB Output is correct
45 Correct 212 ms 54104 KB Output is correct
46 Correct 146 ms 34828 KB Output is correct
47 Correct 158 ms 37448 KB Output is correct
48 Correct 254 ms 42992 KB Output is correct
49 Correct 273 ms 43056 KB Output is correct
50 Correct 131 ms 21732 KB Output is correct
51 Correct 137 ms 21680 KB Output is correct
52 Correct 235 ms 41756 KB Output is correct
53 Correct 242 ms 41820 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 1080 KB Output is correct
2 Correct 8 ms 980 KB Output is correct
3 Correct 7 ms 724 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 10 ms 924 KB Output is correct
6 Correct 11 ms 924 KB Output is correct
7 Correct 12 ms 916 KB Output is correct
8 Correct 8 ms 852 KB Output is correct
9 Correct 8 ms 916 KB Output is correct
10 Correct 7 ms 564 KB Output is correct
11 Correct 10 ms 724 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 788 ms 202196 KB Output is correct
8 Correct 1765 ms 438800 KB Output is correct
9 Correct 1746 ms 440788 KB Output is correct
10 Correct 1745 ms 440968 KB Output is correct
11 Correct 326 ms 169604 KB Output is correct
12 Correct 653 ms 322060 KB Output is correct
13 Correct 677 ms 343224 KB Output is correct

Subtask #7
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 3 ms 1100 KB Output is correct
18 Correct 4 ms 1108 KB Output is correct
19 Correct 3 ms 1108 KB Output is correct
20 Correct 2 ms 852 KB Output is correct
21 Correct 4 ms 880 KB Output is correct
22 Correct 3 ms 852 KB Output is correct
23 Correct 3 ms 852 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 16 ms 4948 KB Output is correct
26 Correct 18 ms 4948 KB Output is correct
27 Correct 16 ms 5064 KB Output is correct
28 Correct 13 ms 3296 KB Output is correct
29 Correct 23 ms 3796 KB Output is correct
30 Correct 19 ms 3764 KB Output is correct
31 Correct 17 ms 3772 KB Output is correct
32 Correct 17 ms 3676 KB Output is correct
33 Correct 139 ms 42540 KB Output is correct
34 Correct 115 ms 36396 KB Output is correct
35 Correct 116 ms 36436 KB Output is correct
36 Correct 87 ms 30084 KB Output is correct
37 Correct 222 ms 57768 KB Output is correct
38 Correct 193 ms 57800 KB Output is correct
39 Correct 210 ms 57892 KB Output is correct
40 Correct 212 ms 54104 KB Output is correct
41 Correct 146 ms 34828 KB Output is correct
42 Correct 158 ms 37448 KB Output is correct
43 Correct 254 ms 42992 KB Output is correct
44 Correct 273 ms 43056 KB Output is correct
45 Correct 131 ms 21732 KB Output is correct
46 Correct 137 ms 21680 KB Output is correct
47 Correct 235 ms 41756 KB Output is correct
48 Correct 242 ms 41820 KB Output is correct
49 Correct 9 ms 1080 KB Output is correct
50 Correct 8 ms 980 KB Output is correct
51 Correct 7 ms 724 KB Output is correct
52 Correct 0 ms 340 KB Output is correct
53 Correct 10 ms 924 KB Output is correct
54 Correct 11 ms 924 KB Output is correct
55 Correct 12 ms 916 KB Output is correct
56 Correct 8 ms 852 KB Output is correct
57 Correct 8 ms 916 KB Output is correct
58 Correct 7 ms 564 KB Output is correct
59 Correct 10 ms 724 KB Output is correct
60 Correct 0 ms 340 KB Output is correct
61 Correct 788 ms 202196 KB Output is correct
62 Correct 1765 ms 438800 KB Output is correct
63 Correct 1746 ms 440788 KB Output is correct
64 Correct 1745 ms 440968 KB Output is correct
65 Correct 326 ms 169604 KB Output is correct
66 Correct 653 ms 322060 KB Output is correct
67 Correct 677 ms 343224 KB Output is correct
68 Correct 0 ms 340 KB Output is correct
69 Correct 0 ms 340 KB Output is correct
70 Correct 1 ms 340 KB Output is correct
71 Correct 1 ms 340 KB Output is correct
72 Correct 0 ms 340 KB Output is correct
73 Correct 1990 ms 585328 KB Output is correct
74 Correct 1704 ms 504416 KB Output is correct
75 Correct 1464 ms 504368 KB Output is correct
76 Correct 1167 ms 423532 KB Output is correct
77 Correct 3285 ms 782000 KB Output is correct
78 Correct 2218 ms 340232 KB Output is correct
79 Correct 2440 ms 366552 KB Output is correct
80 Correct 3796 ms 567016 KB Output is correct
81 Correct 2217 ms 355936 KB Output is correct
82 Correct 2972 ms 474736 KB Output is correct
83 Correct 3699 ms 593116 KB Output is correct
84 Correct 2128 ms 339276 KB Output is correct
85 Correct 3568 ms 579208 KB Output is correct
86 Correct 3476 ms 562364 KB Output is correct
87 Correct 1785 ms 469448 KB Output is correct
88 Correct 3239 ms 778500 KB Output is correct
89 Correct 3238 ms 780160 KB Output is correct
90 Correct 3173 ms 780248 KB Output is correct