Submission #1059417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059417		efishel	Rectangles (IOI19_rect)	C++17	0 / 100	5084 ms	181992 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

const ll MAXN = 1<<12;
const short INF = MAXN+16;
short gi1[MAXN][MAXN], gi2[MAXN][MAXN], gj1[MAXN][MAXN], gj2[MAXN][MAXN];

using dat = pair <pair <short, short>, pair <short, short> >;
dat operator+ (const dat &a, const dat &b) {
    return dat{
        { min(a.first.first, b.first.first),
        min(a.first.second, b.first.second) },
        { max(a.second.first, b.second.first),
        max(a.second.second, b.second.second) }
    };
}

const dat IDEM = { { INF, INF }, { -INF, -INF } };
const dat OVER = { { -INF, -INF }, { INF, INF } };
dat mat[MAXN][MAXN];

ll count_rectangles (vector <vi> a) {
    ll n = a.size(), m = a[0].size();
    for (ll i = 0; i < n; i++) {
        vii stk;
        stk.push_back({ INF, -1 });
        for (ll j = 0; j < m; j++) {
            while (stk.size() && stk.back().first <= a[i][j]) stk.pop_back();
            gj1[i][j] = stk.back().second+1;
            stk.push_back({ a[i][j], j });
        }
    }
    for (ll i = 0; i < n; i++) {
        vii stk;
        stk.push_back({ INF, m });
        for (ll j = m-1; j >= 0; j--) {
            while (stk.size() && stk.back().first <= a[i][j]) stk.pop_back();
            gj2[i][j] = stk.back().second-1;
            stk.push_back({ a[i][j], j });
        }
    }
    for (ll j = 0; j < m; j++) {
        vii stk;
        stk.push_back({ INF, -1 });
        for (ll i = 0; i < n; i++) {
            while (stk.size() && stk.back().first <= a[i][j]) stk.pop_back();
            gi1[i][j] = stk.back().second+1;
            stk.push_back({ a[i][j], i });
        }
    }
    for (ll j = 0; j < m; j++) {
        vii stk;
        stk.push_back({ INF, n });
        for (ll i = n-1; i >= 0; i--) {
            while (stk.size() && stk.back().first <= a[i][j]) stk.pop_back();
            gi2[i][j] = stk.back().second-1;
            stk.push_back({ a[i][j], i });
        }
    }

    priority_queue <pair <ll, ii> > pq;
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < m; j++) {
            pq.push({ -a[i][j], { i, j } });
        }
    }
    for (ll i1 = 0; i1 < max(n,m); i1++) {
        for (ll i2 = 0; i2 < max(n,m); i2++) {
            mat[i1][i2] = OVER;
        }
    }
    ll ans = 0;
    while (pq.size()) {
        auto [i, j] = pq.top().second; pq.pop();
        ll i1 = gi1[i][j];
        ll j1 = gj1[i][j];
        ll i2 = gi2[i][j];
        ll j2 = gj2[i][j];
        mat[i][j] = { { i1, j1 }, { i2, j2 } };
        dat th = IDEM;
        for (ll ii = i1; ii <= i2; ii++)
            for (ll jj = j1; jj <= j2; jj++)
                th = th + mat[ii][jj];
        // cerr << i << ' ' << j << "   ";
        // cerr << i1 << ' ' << j1 << ' ' << i2 << ' ' << j2 << '\n';
        // auto [p1,p2]=s;
        // auto [p3,p4]=p1;
        // auto [p5,p6]=p2;
        // cerr << p3 << ' '<< p4 << ' ' << p5 << ' ' << p6 << '\n';
        if (th == dat{ { i1, j1 }, { i2, j2 } } && 0 < i1 && i2 < n-1 && 0 < j1 && j2 < m-1) ans++;
    }
    return ans;
}

• 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