oj.uz

Submission #791331

# Submission time Handle Problem Language Result Execution time Memory
791331 2023-07-24T02:16:08 Z skittles1412 Rectangles (IOI19_rect) C++17
100 / 100
 4195 ms 563344 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ll = long long;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

namespace __gnu_pbds {
template <typename T>
using ost =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
}

using __gnu_pbds::ost;

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& arr) {
    out << "[";
    for (int i = 0; i < sz(arr); i++) {
        if (i) {
            out << ", ";
        }
        out << arr[i];
    }
    return out << "]";
}

namespace s1 {

constexpr int DIRS[4][2] {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

int n, m;
vector<vector<char>> vis;
vector<vector<int>> arr;

bool ibs(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

template <typename Cb>
void dfs(int x, int y, const Cb& cb) {
    if (!ibs(x, y) || vis[x][y] || arr[x][y]) {
        return;
    }
    cb(x, y);
    vis[x][y] = true;
    for (auto& [dx, dy] : DIRS) {
        dfs(x + dx, y + dy, cb);
    }
}

long solve(const vector<vector<int>>& _arr) {
    arr = _arr;
    n = sz(arr);
    m = sz(arr[0]);
    vis.resize(n, vector<char>(m));

    long ans = 0;

    auto c2 = [&](long n) -> long { return n * (n - 1) / 2; };

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (vis[i][j] || arr[i][j]) {
                continue;
            }
            int mnx = 1e9, mxx = 0, mny = 1e9, mxy = 0, cnt = 0;
            dfs(i, j, [&](int x, int y) -> void {
                mnx = min(mnx, x);
                mxx = max(mxx, x);
                mny = min(mny, y);
                mxy = max(mxy, y);
                cnt++;
            });

            if (cnt == (mxx - mnx + 1) * (mxy - mny + 1) && mnx && mny &&
                mxx < n - 1 && mxy < m - 1) {
                ans++;
            }
        }
    }

    return ans;
}

}  // namespace s1

struct PSA {
    vector<int> psum;

    PSA(const vector<int>& arr) : psum(sz(arr) + 1) {
        partial_sum(begin(arr), end(arr), psum.begin() + 1);
    }

    int query(int l, int r) const {
        return psum[r] - psum[l];
    }
};

vector<pair<int, int>> solve1(const vector<int>& arr) {
    int n = sz(arr);
    vector<pair<int, int>> ans, st;

    st.emplace_back(arr.back(), n - 1);

    for (int i = n - 2; i >= 0; i--) {
        while (sz(st)) {
            if (i + 1 <= st.back().second - 1) {
                dbg(i + 1, st.back().second - 1);
                ans.emplace_back(i + 1, st.back().second - 1);
            }
            if (st.back().first < arr[i]) {
                st.pop_back();
            } else if (st.back().first == arr[i]) {
                st.pop_back();
                break;
            } else {
                break;
            }
        }
        st.emplace_back(arr[i], i);
    }

    assert(sz(ans) <= 2 * n + 10);
    sort(begin(ans), end(ans));

    return ans;
}

template <typename T>
vector<T> set_inter(const vector<T>& a, const vector<T>& b) {
    vector<T> out;
    set_intersection(begin(a), end(a), begin(b), end(b), back_inserter(out));
    return out;
}

template <typename T>
vector<T> set_diff(const vector<T>& a, const vector<T>& b) {
    vector<T> out;
    set_difference(begin(a), end(a), begin(b), end(b), back_inserter(out));
    return out;
}

struct DS1 {
    int n;
    vector<int> arr;
    vector<ost<pair<int, int>>> v;

    DS1(int n) : n(n), arr(n), v(n + 1) {}

    void reset(int _n) {
        n = _n;
        for (int i = 1; i <= n; i++) {
            v[i].clear();
        }
    }

    void update(int ind, int x) {
        if (arr[ind] == x) {
            return;
        }
        int o = ind + 1;
        while (o <= n) {
            v[o].erase({arr[ind], ind});
            if (x) {
                v[o].insert({x, ind});
            }
            o += o & -o;
        }
        arr[ind] = x;
    }

    int query(int ind, int x) const {
        int ans = 0;
        while (ind > 0) {
            ans += sz(v[ind]) - int(v[ind].order_of_key({x + 1, -1}));
            ind -= ind & -ind;
        }
        return ans;
        // return query(1, 0, n - 1, ind - 1, x);
        // int ans = 0;
        // for (int i = 0; i < ind; i++) {
        //     ans += arr[i] > x;
        // }
        // return ans;
    }
};

constexpr int maxn = 7505;

vector<int> e_arr[maxn];
vector<pair<int, int>> e_queries[maxn];

long solve2(int r_shift,
            int n,
            int m,
            const vector<pair<int, int>>& arr,
            const vector<array<int, 3>>& queries) {
    for (int i = 0; i < m; i++) {
        e_arr[i].clear();
        e_queries[i].clear();
    }
    n -= r_shift;
    for (auto& [ind, x] : arr) {
        e_arr[ind].push_back(x - r_shift);
        dbg(ind, x - r_shift);
    }
    for (auto& [x, ql, qr] : queries) {
        e_queries[ql].emplace_back(x - r_shift, qr);
        dbg(ql, qr, x - r_shift);
    }

    long ans = 0;

    DS1 ds(n);
    vector<int> p_arr;

    for (int i = m - 1; i >= 0; i--) {
        // sort(begin(e_arr[i]), end(e_arr[i]));
        for (auto& x : set_diff(p_arr, e_arr[i])) {
            ds.update(x, 0);
        }
        p_arr = e_arr[i];

        for (auto& a : e_arr[i]) {
            if (!ds.arr[a]) {
                ds.update(a, i);
            }
        }

        for (auto& [x, qr] : e_queries[i]) {
            dbg(x, n);
            ans += ds.query(x + 1, qr - 1);
        }
    }

    return ans;
}

ll count_rectangles(vector<vector<int>> arr) {
    int n = sz(arr), m = sz(arr[0]);

    {
        bool ok = true;
        for (auto& a : arr) {
            for (auto& b : a) {
                ok &= 0 <= b && b <= 1;
            }
        }
        if (ok) {
            return s1::solve(arr);
        }
    }

    vector<pair<int, int>> r_res[n], c_res[m];
    for (int i = 0; i < n; i++) {
        r_res[i] = solve1(arr[i]);
    }
    for (int i = 0; i < m; i++) {
        vector<int> tmp;
        for (int j = 0; j < n; j++) {
            tmp.push_back(arr[j][i]);
        }
        c_res[i] = solve1(tmp);
    }

    vector<int> r_good[m][m];
    for (int i = 0; i < n; i++) {
        for (auto& [ql, qr] : r_res[i]) {
            r_good[ql][qr].push_back(i);
        }
    }

    vector<array<int, 3>> queries[n];

    for (int cl = 0; cl < m; cl++) {
        for (int cr = cl; cr < m; cr++) {
            auto& carr = r_good[cl][cr];

            for (int i = 0; i < sz(carr);) {
                int ci = i;
                for (i++; i < sz(carr) && carr[i - 1] + 1 == carr[i]; i++)
                    ;
                int cql = carr[ci], cqr = carr[i - 1];
                cql = max(cql, 1);
                cqr = min(cqr, n - 2);

                for (int j = cql; j <= cqr; j++) {
                    queries[j].push_back({cqr, cl, cr});
                }
            }
        }
    }

    long ans = 0;

    vector<pair<int, int>> rvals[n];
    for (int i = 0; i < m; i++) {
        for (auto& [rql, rqr] : c_res[i]) {
            rvals[rql].emplace_back(i, rqr);
        }
    }

    for (int r = 0; r < n; r++) {
        ans += solve2(r, n, m, rvals[r], queries[r]);
        dbg(r, sz(rvals[r]), sz(queries[r]), ans);
    }

    return ans;
}

Compilation message

rect.cpp: In function 'int64_t s1::solve(const std::vector<std::vector<int> >&)':
rect.cpp:81:10: warning: variable 'c2' set but not used [-Wunused-but-set-variable]
   81 |     auto c2 = [&](long n) -> long { return n * (n - 1) / 2; };
      |          ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 0 ms 596 KB Output is correct
14 Correct 0 ms 596 KB Output is correct
15 Correct 0 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 0 ms 596 KB Output is correct
14 Correct 0 ms 596 KB Output is correct
15 Correct 0 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 2 ms 1236 KB Output is correct
23 Correct 2 ms 1236 KB Output is correct
24 Correct 2 ms 1236 KB Output is correct
25 Correct 2 ms 980 KB Output is correct
26 Correct 3 ms 1236 KB Output is correct
27 Correct 3 ms 1236 KB Output is correct
28 Correct 3 ms 1236 KB Output is correct
29 Correct 2 ms 852 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 0 ms 596 KB Output is correct
14 Correct 0 ms 596 KB Output is correct
15 Correct 0 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 2 ms 1236 KB Output is correct
18 Correct 2 ms 1236 KB Output is correct
19 Correct 2 ms 1236 KB Output is correct
20 Correct 2 ms 980 KB Output is correct
21 Correct 3 ms 1236 KB Output is correct
22 Correct 3 ms 1236 KB Output is correct
23 Correct 3 ms 1236 KB Output is correct
24 Correct 2 ms 852 KB Output is correct
25 Correct 1 ms 596 KB Output is correct
26 Correct 1 ms 596 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 6 ms 4020 KB Output is correct
31 Correct 6 ms 3924 KB Output is correct
32 Correct 7 ms 3924 KB Output is correct
33 Correct 11 ms 3028 KB Output is correct
34 Correct 19 ms 4180 KB Output is correct
35 Correct 20 ms 4180 KB Output is correct
36 Correct 19 ms 4180 KB Output is correct
37 Correct 18 ms 4052 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 0 ms 596 KB Output is correct
14 Correct 0 ms 596 KB Output is correct
15 Correct 0 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 2 ms 1236 KB Output is correct
18 Correct 2 ms 1236 KB Output is correct
19 Correct 2 ms 1236 KB Output is correct
20 Correct 2 ms 980 KB Output is correct
21 Correct 3 ms 1236 KB Output is correct
22 Correct 3 ms 1236 KB Output is correct
23 Correct 3 ms 1236 KB Output is correct
24 Correct 2 ms 852 KB Output is correct
25 Correct 6 ms 4020 KB Output is correct
26 Correct 6 ms 3924 KB Output is correct
27 Correct 7 ms 3924 KB Output is correct
28 Correct 11 ms 3028 KB Output is correct
29 Correct 19 ms 4180 KB Output is correct
30 Correct 20 ms 4180 KB Output is correct
31 Correct 19 ms 4180 KB Output is correct
32 Correct 18 ms 4052 KB Output is correct
33 Correct 1 ms 596 KB Output is correct
34 Correct 1 ms 596 KB Output is correct
35 Correct 1 ms 596 KB Output is correct
36 Correct 1 ms 596 KB Output is correct
37 Correct 1 ms 596 KB Output is correct
38 Correct 111 ms 36692 KB Output is correct
39 Correct 112 ms 39220 KB Output is correct
40 Correct 226 ms 38044 KB Output is correct
41 Correct 199 ms 40452 KB Output is correct
42 Correct 74 ms 44252 KB Output is correct
43 Correct 74 ms 44160 KB Output is correct
44 Correct 76 ms 44236 KB Output is correct
45 Correct 71 ms 42688 KB Output is correct
46 Correct 18 ms 6996 KB Output is correct
47 Correct 114 ms 30124 KB Output is correct
48 Correct 264 ms 45536 KB Output is correct
49 Correct 278 ms 45636 KB Output is correct
50 Correct 140 ms 20180 KB Output is correct
51 Correct 129 ms 29128 KB Output is correct
52 Correct 228 ms 44168 KB Output is correct
53 Correct 238 ms 44120 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 148064 KB Output is correct
2 Correct 59 ms 106824 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 81 ms 147840 KB Output is correct
6 Correct 80 ms 147832 KB Output is correct
7 Correct 80 ms 147916 KB Output is correct
8 Correct 82 ms 148012 KB Output is correct
9 Correct 85 ms 147852 KB Output is correct
10 Correct 80 ms 147580 KB Output is correct
11 Correct 80 ms 147616 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 0 ms 596 KB Output is correct
7 Correct 110 ms 37244 KB Output is correct
8 Correct 233 ms 80108 KB Output is correct
9 Correct 233 ms 80520 KB Output is correct
10 Correct 234 ms 80432 KB Output is correct
11 Correct 163 ms 152780 KB Output is correct
12 Correct 324 ms 363084 KB Output is correct
13 Correct 391 ms 430452 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 0 ms 596 KB Output is correct
14 Correct 0 ms 596 KB Output is correct
15 Correct 0 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 2 ms 1236 KB Output is correct
18 Correct 2 ms 1236 KB Output is correct
19 Correct 2 ms 1236 KB Output is correct
20 Correct 2 ms 980 KB Output is correct
21 Correct 3 ms 1236 KB Output is correct
22 Correct 3 ms 1236 KB Output is correct
23 Correct 3 ms 1236 KB Output is correct
24 Correct 2 ms 852 KB Output is correct
25 Correct 6 ms 4020 KB Output is correct
26 Correct 6 ms 3924 KB Output is correct
27 Correct 7 ms 3924 KB Output is correct
28 Correct 11 ms 3028 KB Output is correct
29 Correct 19 ms 4180 KB Output is correct
30 Correct 20 ms 4180 KB Output is correct
31 Correct 19 ms 4180 KB Output is correct
32 Correct 18 ms 4052 KB Output is correct
33 Correct 111 ms 36692 KB Output is correct
34 Correct 112 ms 39220 KB Output is correct
35 Correct 226 ms 38044 KB Output is correct
36 Correct 199 ms 40452 KB Output is correct
37 Correct 74 ms 44252 KB Output is correct
38 Correct 74 ms 44160 KB Output is correct
39 Correct 76 ms 44236 KB Output is correct
40 Correct 71 ms 42688 KB Output is correct
41 Correct 18 ms 6996 KB Output is correct
42 Correct 114 ms 30124 KB Output is correct
43 Correct 264 ms 45536 KB Output is correct
44 Correct 278 ms 45636 KB Output is correct
45 Correct 140 ms 20180 KB Output is correct
46 Correct 129 ms 29128 KB Output is correct
47 Correct 228 ms 44168 KB Output is correct
48 Correct 238 ms 44120 KB Output is correct
49 Correct 86 ms 148064 KB Output is correct
50 Correct 59 ms 106824 KB Output is correct
51 Correct 1 ms 1108 KB Output is correct
52 Correct 1 ms 596 KB Output is correct
53 Correct 81 ms 147840 KB Output is correct
54 Correct 80 ms 147832 KB Output is correct
55 Correct 80 ms 147916 KB Output is correct
56 Correct 82 ms 148012 KB Output is correct
57 Correct 85 ms 147852 KB Output is correct
58 Correct 80 ms 147580 KB Output is correct
59 Correct 80 ms 147616 KB Output is correct
60 Correct 0 ms 596 KB Output is correct
61 Correct 110 ms 37244 KB Output is correct
62 Correct 233 ms 80108 KB Output is correct
63 Correct 233 ms 80520 KB Output is correct
64 Correct 234 ms 80432 KB Output is correct
65 Correct 163 ms 152780 KB Output is correct
66 Correct 324 ms 363084 KB Output is correct
67 Correct 391 ms 430452 KB Output is correct
68 Correct 1 ms 596 KB Output is correct
69 Correct 1 ms 596 KB Output is correct
70 Correct 1 ms 596 KB Output is correct
71 Correct 1 ms 596 KB Output is correct
72 Correct 1 ms 596 KB Output is correct
73 Correct 1729 ms 437272 KB Output is correct
74 Correct 1516 ms 495052 KB Output is correct
75 Correct 3599 ms 483892 KB Output is correct
76 Correct 3283 ms 515372 KB Output is correct
77 Correct 1098 ms 554012 KB Output is correct
78 Correct 2244 ms 396060 KB Output is correct
79 Correct 2635 ms 318120 KB Output is correct
80 Correct 4009 ms 552576 KB Output is correct
81 Correct 2427 ms 413168 KB Output is correct
82 Correct 3293 ms 403828 KB Output is correct
83 Correct 4195 ms 563344 KB Output is correct
84 Correct 1967 ms 389248 KB Output is correct
85 Correct 3588 ms 540236 KB Output is correct
86 Correct 3417 ms 528640 KB Output is correct
87 Correct 658 ms 305996 KB Output is correct
88 Correct 1106 ms 553376 KB Output is correct
89 Correct 1106 ms 553636 KB Output is correct
90 Correct 1104 ms 553764 KB Output is correct