Submission #1312244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312244		qilby	Rectangles (IOI19_rect)	C++20	100 / 100	2611 ms	1023628 KiB

rect

#include <bits/stdc++.h>

#include "rect.h"

using namespace std;
using ll = long long;

const int N = 2509;

set < int > g[N][N];
vector < int > all[N][N];
int n, m, lft[N], rgt[N];
map < int , int > f[N];

ll count_rectangles(vector < vector < int > > a) {
    n = (int)a.size(), m = (int)a[0].size();

    for (int i = 0; i < n; i++) {
        vector < int > v;

        for (int j = 0; j < m; j++) {
            while (!v.empty() && a[i][v.back()] <= a[i][j]) v.pop_back();
            if (v.empty()) lft[j] = -1; else lft[j] = v.back();
            v.push_back(j);
        }

        v.clear();

        for (int j = m - 1; j >= 0; j--) {
            while (!v.empty() && a[i][v.back()] <= a[i][j]) v.pop_back();
            if (v.empty()) rgt[j] = -1; else rgt[j] = v.back();
            v.push_back(j);
        }

        for (int j = 0; j < m; j++) if (lft[j] >= 0 && rgt[j] >= 0) {
            all[lft[j] + 1][rgt[j] - 1].push_back(i);
        }
    }

    for (int j = 0; j < m; j++) {
        vector < int > v;

        for (int i = 0; i < n; i++) {
            while (!v.empty() && a[v.back()][j] <= a[i][j]) v.pop_back();
            if (v.empty()) lft[i] = -1; else lft[i] = v.back();
            v.push_back(i);
        }

        v.clear();

        for (int i = n - 1; i >= 0; i--) {
            while (!v.empty() && a[v.back()][j] <= a[i][j]) v.pop_back();
            if (v.empty()) rgt[i] = -1; else rgt[i] = v.back();
            v.push_back(i);
        }

        for (int i = 0; i < n; i++) if (lft[i] >= 0 && rgt[i] >= 0) {
            int lg = lft[i] + 1, rg = rgt[i] - 1;
            g[j][lg].insert(rg);
        }
    }

    for (int j = m - 1; j >= 0; j--) {
        for (int il = 0; il < n; il++) {
            for (int ir : g[j][il]) {
                int x = il * n + ir;
                if (g[j + 1][il].find(ir) == g[j + 1][il].end()) f[j][x] = j;
                else f[j][x] = f[j + 1][x];
            }
        }
    }

    ll res = 0;

    for (int jl = 0; jl < m; jl++) {
        for (int jr = jl; jr < m; jr++) if (!all[jl][jr].empty()) {
            int p = 0;
            sort(all[jl][jr].begin(), all[jl][jr].end());

            while (p < (int)all[jl][jr].size()) {
                int l = p;
                while (l + 1 < (int)all[jl][jr].size() && all[jl][jr][l + 1] - all[jl][jr][l] <= 1) l++;

                int il = all[jl][jr][p], ir = all[jl][jr][l];

                for (int i1 = il; i1 <= ir; i1++) {
                    for (int i2 : g[jl][i1]) {
                        if (i2 > ir) break;
                        if (f[jl][i1 * n + i2] >= jr) res++;
                    }
                }

                p = l + 1;
            }
        }
    }

    return res;
}

/*int main() {
	int n, m;
	cin >> n >> m;

	vector < vector < int > > a(n, vector < int > (m));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) cin >> a[i][j];
	}

	cout << count_rectangles(a);
}*/

• 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: 28 / 28