Submission #1069050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069050		RaresFelix	Rectangles (IOI19_rect)	C++17	59 / 100	5016 ms	662900 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;

vector<pair<ii, ii> > get_linii(vector<vi> &a) {
    int n = int(a.size()), m = int(a[0].size());
    vector<set<ii> > Perechi(n);
    for(int i = 1; i + 1 < n; ++i) {
        vector<ii> ord;
        for(int j = 0; j < m; ++j)
            ord.push_back({a[i][j], j});
        sort(ord.rbegin(), ord.rend());
        set<int> Poz;

        int p2 = 0;
        for(int j = 0; j < m; ++j) {
            auto [v, p] = ord[j];
            while(p2 < m && ord[p2].first == v) {
                Poz.insert(ord[p2].second);
                ++p2;
            }
            if(1) {
                auto it = Poz.lower_bound(p);
                ++it;
                if(it != Poz.end()) {
                    if(*it > p + 1)
                        Perechi[i].insert(ii{p, *it});
                }
            }
            if(1) {
                auto it = Poz.lower_bound(p);
                if(it != Poz.begin()) {
                    --it;
                    if(p > *it + 1)
                        Perechi[i].insert(ii{*it, p});
                }
            }
        }
    }
    vector<pair<ii, ii> > Re;
    for(int i = 0; i < n; ++i) {
        for(auto it : Perechi[i]) {
            int p = i;
            while(p + 1 < n && Perechi[p + 1].count(it)) ++p;
            Re.push_back({{i - 1, p + 1}, it});
            for(int j = i + 1; j <= p; ++j)
                Perechi[j].erase(it);
        }
    }
    return Re;
}

struct AIB2D {
    int n, m;
    vector<vi> V;
    AIB2D(int N, int M) : n(N + 1), m(M + 1), V(N + 1, vi(M + 1, 0)) {}

    void update(int l, int c, int v) {
        ++l; ++c;
        while (l < n) {
            int p = c;
            while (p < m) {
                V[l][p] += v;
                p += p & -p;
            }
            l += l & -l;
        }
    }

    int query(int l, int c) {
        ++l; ++c;
        int re = 0;
        while (l) {
            int p = c;
            while (p) {
                re += V[l][p];
                p -= p & -p;
            }
            l -= l & -l;
        }
        return re;
    }
};

ll count_rectangles(vector<vi> a) {
    int n = int(a.size()), m = int(a[0].size());
    vector<vi> b(m, vi(n, 0));
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            b[j][i] = a[i][j];
    auto V = get_linii(a), H = get_linii(b);
    for(auto &[x, y] : H) swap(x, y);
    auto inclus = [&](ii a, ii b) {
        ///b inclus in a
        return b.first >= a.first && b.second <= a.second;
    };
    int re = 0;
    vector< vector<vector<ii> > > LinV(n, vector(m, vector<ii>()));
    auto LinH = LinV;
    for(auto [x, y] : V) {
        for(int i = x.first; i <= x.second; ++i) {
            LinV[i][y.second].push_back({i - x.first, y.second - y.first});
        }
    }
    for(auto [x, y] : H) {
        for(int j = y.first; j <= y.second; ++j) {
            LinH[x.second][j].push_back({x.second - x.first, j - y.first});
        }
    }
    AIB2D Sol(n, m);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            for(auto [xh, yh] : LinH[i][j]) {
                Sol.update(xh, m - yh - 1, 1);
            }
            for(auto [xv, yv] : LinV[i][j]) {
                int v = Sol.query(xv, m - yv - 1);
                if(v) {
                    re += v;
                }
            }
            for(auto [xh, yh] : LinH[i][j]) {
                Sol.update(xh, m - yh - 1, -1);
            }
        }
    }
	return re;
}

Compilation message (stderr)

rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:98:10: warning: variable 'inclus' set but not used [-Wunused-but-set-variable]
   98 |     auto inclus = [&](ii a, ii b) {
      |          ^~~~~~

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