Submission #820846

#	Time	Username	Problem	Language	Result	Execution time	Memory
820846		resting	Rectangles (IOI19_rect)	C++17	72 / 100	2260 ms	1048576 KiB

rect

//#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<map<short, short>>> vert, hori; // idfc
    vert = hori = vector<vector<map<short, short>>>(n, vector<map<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]][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][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;
            if (i + 1 < n) {
                for (auto& x : hori[i][j]) {
                    x.second += hori[i + 1][j][x.first];
                }
            }
            if (j + 1 < m) {
                for (auto& x : vert[i][j]) {
                    x.second += vert[i][j + 1][x.first];
                }
            }
            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 (stderr)

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:96: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]
   96 |                 while (cur < bruh.size() && bruh[cur].first < x.first) {
      |                        ~~~~^~~~~~~~~~~~~
rect.cpp:102: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]
  102 |             while (cur < bruh.size()) {
      |                    ~~~~^~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28