Submission #1303650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303650		andrei_iorgulescu	Rectangles (IOI19_rect)	C++20	72 / 100	5145 ms	949788 KiB

rect

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

using namespace std;

int n, m;
int a[2505][2505];
int dr[2505][2505], st[2505][2505], sus[2505][2505], jos[2505][2505];///ultimul pe care il bate in directia aia
int lg[2505];
short int rmqdr[13][2505][2505], rmqjos[13][2505][2505];
short int rmqst[13][2505][2505], rmqsus[13][2505][2505];
int dr2[2505][2505], st2[2505][2505], sus2[2505][2505], jos2[2505][2505];

struct gg
{
    int x1, y1, x2, y2;
};

int query_dr(int col, int l, int r)
{
    int lgg = lg[r - l + 1];
    return min(rmqdr[lgg][l][col], rmqdr[lgg][r - (1 << lgg) + 1][col]);
}

int query_st(int col, int l, int r)
{
    int lgg = lg[r - l + 1];
    return max(rmqst[lgg][l][col], rmqst[lgg][r - (1 << lgg) + 1][col]);
}

int query_sus(int lin, int l, int r)
{
    int lgg = lg[r - l + 1];
    return max(rmqsus[lgg][lin][l], rmqsus[lgg][lin][r - (1 << lgg) + 1]);
}

int query_jos(int lin, int l, int r)
{
    int lgg = lg[r - l + 1];
    return min(rmqjos[lgg][lin][l], rmqjos[lgg][lin][r - (1 << lgg) + 1]);
}

bool ok(gg k)
{
    int x1 = k.x1, x2 = k.x2, y1 = k.y1, y2 = k.y2;
    if (x1 > x2 or y1 > y2 or x1 <= 1 or x2 >= n or y1 <= 1 or y2 >= m)
        return false;
    int f1 = query_dr(y1 - 1, x1, x2);
    int f2 = query_st(y2 + 1, x1, x2);
    int f3 = query_jos(x1 - 1, y1, y2);
    int f4 = query_sus(x2 + 1, y1, y2);
    gg ret;
    if (f1 >= y2 and f2 <= y1 and f3 >= x2 and f4 <= x1)
        return true;
    return false;
}

long long count_rectangles(vector<vector<int>> A)
{
    n = A.size();
    m = A[0].size();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = A[i - 1][j - 1];
    for (int i = 1; i <= n; i++)
    {
        stack<int> s;
        for (int j = 1; j <= m; j++)
        {
            while (!s.empty() and a[i][j] > a[i][s.top()])
                s.pop();
            if (s.empty())
                st[i][j] = 1;
            else
                st[i][j] = s.top() + 1;
            s.push(j);
        }
        while (!s.empty())
            s.pop();
        for (int j = m; j >= 1; j--)
        {
            while (!s.empty() and a[i][j] > a[i][s.top()])
                s.pop();
            if (s.empty())
                dr[i][j] = m;
            else
                dr[i][j] = s.top() - 1;
            s.push(j);
        }
        while (!s.empty())
            s.pop();
    }
    for (int i = 1; i <= m; i++)
    {
        stack<int> s;
        for (int j = 1; j <= n; j++)
        {
            while (!s.empty() and a[j][i] > a[s.top()][i])
                s.pop();
            if (s.empty())
                sus[j][i] = 1;
            else
                sus[j][i] = s.top() + 1;
            s.push(j);
        }
        while (!s.empty())
            s.pop();
        for (int j = n; j >= 1; j--)
        {
            while (!s.empty() and a[j][i] > a[s.top()][i])
                s.pop();
            if (s.empty())
                jos[j][i] = n;
            else
                jos[j][i] = s.top() - 1;
            s.push(j);
        }
        while (!s.empty())
            s.pop();
    }
    for (int i = 2; i <= 2500; i++)
        lg[i] = 1 + lg[i / 2];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            rmqdr[0][i][j] = dr[i][j];
            rmqst[0][i][j] = st[i][j];
            rmqsus[0][i][j] = sus[i][j];
            rmqjos[0][i][j] = jos[i][j];
        }
    }
    for (int pas = 1; pas <= 12; pas++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m - (1 << pas) + 1; j++)
            {
                rmqjos[pas][i][j] = min(rmqjos[pas - 1][i][j], rmqjos[pas - 1][i][j + (1 << (pas - 1))]);
                rmqsus[pas][i][j] = max(rmqsus[pas - 1][i][j], rmqsus[pas - 1][i][j + (1 << (pas - 1))]);
            }
        }
        for (int j = 1; j <= m; j++)
        {
            for (int i = 1; i <= n - (1 << pas) + 1; i++)
            {
                rmqdr[pas][i][j] = min(rmqdr[pas - 1][i][j], rmqdr[pas - 1][i + (1 << (pas - 1))][j]);
                rmqst[pas][i][j] = max(rmqst[pas - 1][i][j], rmqst[pas - 1][i + (1 << (pas - 1))][j]);
            }
        }
    }
    vector<gg> sol;
    for (int i = 1; i <= n; i++)
    {
        stack<int> s;
        for (int j = 1; j <= m; j++)
        {
            while (!s.empty() and a[i][j] >= a[i][s.top()])
                s.pop();
            if (s.empty())
                st2[i][j] = 1;
            else
                st2[i][j] = s.top() + 1;
            s.push(j);
        }
        while (!s.empty())
            s.pop();
        for (int j = m; j >= 1; j--)
        {
            while (!s.empty() and a[i][j] >= a[i][s.top()])
                s.pop();
            if (s.empty())
                dr2[i][j] = m;
            else
                dr2[i][j] = s.top() - 1;
            s.push(j);
        }
        while (!s.empty())
            s.pop();
    }
    for (int i = 1; i <= m; i++)
    {
        stack<int> s;
        for (int j = 1; j <= n; j++)
        {
            while (!s.empty() and a[j][i] >= a[s.top()][i])
                s.pop();
            if (s.empty())
                sus2[j][i] = 1;
            else
                sus2[j][i] = s.top() + 1;
            s.push(j);
        }
        while (!s.empty())
            s.pop();
        for (int j = n; j >= 1; j--)
        {
            while (!s.empty() and a[j][i] >= a[s.top()][i])
                s.pop();
            if (s.empty())
                jos2[j][i] = n;
            else
                jos2[j][i] = s.top() - 1;
            s.push(j);
        }
        while (!s.empty())
            s.pop();
    }
    for (int i = 2; i < n; i++)
    {
        for (int j = 2; j < m; j++)
        {
            gg aux;
            aux.x1 = sus2[i][j];
            aux.x2 = jos2[i][j];
            aux.y1 = st2[i][j];
            aux.y2 = dr2[i][j];
            if (ok(aux))
                sol.push_back(aux);
        }
    }
    sort(sol.begin(), sol.end(), [](gg u, gg v){
         vector<int> vu = {u.x1, u.y1, u.x2, u.y2};
         vector<int> vv = {v.x1, v.y1, v.x2, v.y2};
         return vu < vv;
    });
    if (sol.empty())
        return 0ll;
    long long rs = 1;
    for (int i = 1; i < sol.size(); i++)
        if (sol[i].x1 != sol[i - 1].x1 or sol[i].y1 != sol[i - 1].y1 or sol[i].x2 != sol[i - 1].x2 or sol[i].y2 != sol[i - 1].y2)
            rs++;
    return rs;
}

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