Submission #1068998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068998		RaresFelix	Rectangles (IOI19_rect)	C++17	0 / 100	11 ms	1332 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 = 0; i < 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;
        for(auto [v, p] : ord) {
            auto it = Poz.lower_bound(p);
            if(it != Poz.end()) {
                if(*it > p + 1)
                    Perechi[i].insert(ii{p, *it});
            }
            if(it != Poz.begin()) {
                --it;
                if(p > *it + 1)
                    Perechi[i].insert(ii{*it, p});
            }
            Poz.insert(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;
}

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 H = get_linii(a), V = get_linii(b);
    for(auto &[x, y] : V) 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;
    for(auto [x1, y1] : H) {
        for(auto [x2, y2] : V) {
            re += inclus(x1, x2) && inclus(y2, y1);
           // if(v) {
           //     printf("(%d %d) (%d %d)  | ", x1.first, x1.second, y1.first, y1.second);
           //     printf("(%d %d) (%d %d)\n", x2.first, x2.second, y2.first, y2.second);
           // }
        }
    }
  //  for(auto [x, y] : V) {
  //      printf("(%d %d) (%d %d)\n", x.first, x.second, y.first, y.second);
  //  }
	return re;
}

• 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