Submission #796753

#	Time	Username	Problem	Language	Result	Execution time	Memory
796753		lukameladze	Rectangles (IOI19_rect)	C++17	72 / 100	2919 ms	1048576 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <short, short>
#define pb push_back
const int N = 2501;
short n, m, sf[N][N], pr[N][N], pr_u[N][N], sf_d[N][N];
int a[N][N];
set <pii> s[N], sj[N];
set <array <short , 3> > dp[N], dpj[N];
short get(short i, short l, short r) {
    auto it = dp[i].lower_bound({l, r, 0});
    short res = 0;
    if ((*it)[0] == l && (*it)[1] == r) {
        res = (*it)[2];
    }
    return res;
}
short getj(short j, short l, short r) {
    auto it = dpj[j].lower_bound({l, r, 0});
    short res = 0;
    if ((*it)[0] == l && (*it)[1] == r) {
        res = (*it)[2];
    }
    return res;
}
long long count_rectangles(vector<vector<int> > x) {
    n = x.size();
    for (int i = 0; i < n; i++) {
        m = x[i].size();
        for (int j = 0; j < m; j++) {
            a[i][j] = x[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int cur = j - 1;
            while (cur >= 0 && a[i][cur] <= a[i][j]) {
                cur = pr[i][cur];
            }
            pr[i][j] = cur;
        }
        for (int j = m - 1; j >= 0; j--) {
            int cur = j + 1;
            while (cur < m && a[i][cur] <= a[i][j]) {
                cur = sf[i][cur];
            }
            sf[i][j] = cur;
            int l = pr[i][j] + 1, r = sf[i][j] - 1;
            if (l != 0 && r != m - 1) s[i].insert({l, r});
        }
    }

    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++) {
            int cur = i - 1;
            while (cur >= 0 && a[cur][j] <= a[i][j]) {
                cur = pr_u[cur][j];
            }
            pr_u[i][j] = cur;
        }
        for (int i = n - 1; i >= 0; i--) {
            int cur = i + 1;
            while (cur < n && a[cur][j] <= a[i][j]) {
                cur = sf_d[cur][j];
            }
            sf_d[i][j] = cur;
            int l = pr_u[i][j] + 1, r = sf_d[i][j] - 1;
            if (l != 0 && r != n - 1) sj[j].insert({l, r});
        }
    }
    for (int i = 0; i < n; i++) {
        for (pii sth : s[i]) {
            int l = sth.f, r = sth.s;
            if (i == 0) {
                dp[i].insert({l, r, 1});
                continue;
            }
            dp[i].insert({l, r, get(i - 1, l, r) + 1});
        }
    }
    for (int j = 0; j < m; j++) {
        for (pii sth : sj[j]) {
            int l = sth.f, r = sth.s;
            if (j == 0) {
                dpj[j].insert({l, r, 1});
                continue;
            }
            dpj[j].insert({l, r, getj(j - 1, l, r) + 1});
        }
    }
    set <array <short, 4> > ans;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int xu = pr_u[i][j] + 1, yu = pr[i][j] + 1;
            int xd = sf_d[i][j] - 1, yd = sf[i][j] - 1;
            if (xu == 0 || yu == 0 || xd == n - 1 || yd == m - 1) continue;
            if (get(xd, yu, yd) >= (xd - xu + 1) && getj(yd, xu, xd) >= (yd - yu + 1)) ans.insert({xu, yu, xd, yd});
        }
    }
    return (int)ans.size();
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:78:31: warning: narrowing conversion of 'l' from 'int' to 'short int' [-Wnarrowing]
   78 |                 dp[i].insert({l, r, 1});
      |                               ^
rect.cpp:78:34: warning: narrowing conversion of 'r' from 'int' to 'short int' [-Wnarrowing]
   78 |                 dp[i].insert({l, r, 1});
      |                                  ^
rect.cpp:81:27: warning: narrowing conversion of 'l' from 'int' to 'short int' [-Wnarrowing]
   81 |             dp[i].insert({l, r, get(i - 1, l, r) + 1});
      |                           ^
rect.cpp:81:30: warning: narrowing conversion of 'r' from 'int' to 'short int' [-Wnarrowing]
   81 |             dp[i].insert({l, r, get(i - 1, l, r) + 1});
      |                              ^
rect.cpp:81:50: warning: narrowing conversion of '(((int)get(((int)((short int)(i - 1))), ((int)((short int)l)), ((int)((short int)r)))) + 1)' from 'int' to 'short int' [-Wnarrowing]
   81 |             dp[i].insert({l, r, get(i - 1, l, r) + 1});
      |                                 ~~~~~~~~~~~~~~~~~^~~
rect.cpp:88:32: warning: narrowing conversion of 'l' from 'int' to 'short int' [-Wnarrowing]
   88 |                 dpj[j].insert({l, r, 1});
      |                                ^
rect.cpp:88:35: warning: narrowing conversion of 'r' from 'int' to 'short int' [-Wnarrowing]
   88 |                 dpj[j].insert({l, r, 1});
      |                                   ^
rect.cpp:91:28: warning: narrowing conversion of 'l' from 'int' to 'short int' [-Wnarrowing]
   91 |             dpj[j].insert({l, r, getj(j - 1, l, r) + 1});
      |                            ^
rect.cpp:91:31: warning: narrowing conversion of 'r' from 'int' to 'short int' [-Wnarrowing]
   91 |             dpj[j].insert({l, r, getj(j - 1, l, r) + 1});
      |                               ^
rect.cpp:91:52: warning: narrowing conversion of '(((int)getj(((int)((short int)(j - 1))), ((int)((short int)l)), ((int)((short int)r)))) + 1)' from 'int' to 'short int' [-Wnarrowing]
   91 |             dpj[j].insert({l, r, getj(j - 1, l, r) + 1});
      |                                  ~~~~~~~~~~~~~~~~~~^~~
rect.cpp:100:100: warning: narrowing conversion of 'xu' from 'int' to 'short int' [-Wnarrowing]
  100 |             if (get(xd, yu, yd) >= (xd - xu + 1) && getj(yd, xu, xd) >= (yd - yu + 1)) ans.insert({xu, yu, xd, yd});
      |                                                                                                    ^~
rect.cpp:100:104: warning: narrowing conversion of 'yu' from 'int' to 'short int' [-Wnarrowing]
  100 |             if (get(xd, yu, yd) >= (xd - xu + 1) && getj(yd, xu, xd) >= (yd - yu + 1)) ans.insert({xu, yu, xd, yd});
      |                                                                                                        ^~
rect.cpp:100:108: warning: narrowing conversion of 'xd' from 'int' to 'short int' [-Wnarrowing]
  100 |             if (get(xd, yu, yd) >= (xd - xu + 1) && getj(yd, xu, xd) >= (yd - yu + 1)) ans.insert({xu, yu, xd, yd});
      |                                                                                                            ^~
rect.cpp:100:112: warning: narrowing conversion of 'yd' from 'int' to 'short int' [-Wnarrowing]
  100 |             if (get(xd, yu, yd) >= (xd - xu + 1) && getj(yd, xu, xd) >= (yd - yu + 1)) ans.insert({xu, yu, xd, yd});
      |                                                                                                                ^~

• 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