Submission #820534

#	Time	Username	Problem	Language	Result	Execution time	Memory
820534		resting	Rectangles (IOI19_rect)	C++17	0 / 100	2 ms	724 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]) r[a]++;
        p[b] = a;
        l[a] = min(l[a], l[b]);
        r[a] = max(r[a], r[b]);
    }
};


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<int>> a) {
    int n = a.size(), m = a[0].size();
    vector<vector<map<int, int>>> vert, hori; // idfc
    for (int i = 0; i < n; i++) {
        vector<pair<int, int>> v;
        vector<int> vis(m, 0);
        for (int j = 0; j < m; j++) v.push_back(make_pair(a[i][j], j));
        dsu ac(m);
        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;
            }
        }
    }

    for (int i = 0; i < m; i++) {
        vector<pair<int, int>> v;
        vector<int> vis(n, 0);
        for (int j = 0; j < n; j++) v.push_back(make_pair(a[j][i], j));
        dsu ac(n);
        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;
            }
        }
    }

    long long res = 0;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (i + 1 < n) {
                for (auto& x : vert[i][j]) {
                    x.second += vert[i + 1][j][x.first];
                }
            }
            if (j + 1 < m) {
                for (auto& x : hori[i][j]) {
                    x.second += hori[i][j + 1][x.first];
                }
            }
            vector<pair<int, int>> bruh;
            for (auto& x : vert[i][j]) bruh.push_back(make_pair(x.second, x.first));
            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);
            }
        }
    }
    return res;
}

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

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