Submission #260067

#	Time	Username	Problem	Language	Result	Execution time	Memory
260067		dandrozavr	Rectangles (IOI19_rect)	C++14	10 / 100	5063 ms	7416 KiB

rect

/*
Uruchamiamy samolot zwiadowczy ( + 500% do wzlamaniej )

/▄/  /█/  /◐/  /▐/   /▌/ /▀/ /░/ /  / choose your own style!

***IT'S OUR LONG WAY TO THE OIILLLL***


░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀  ░░░░░░░░███░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░█▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▀██████████████████████████████████████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄████▄████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████
░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█████████▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀  ░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░░░░░░░░░░░░░░░
*/


//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

#include <bits/stdc++.h>
using namespace std ;
#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;
namespace fastio {template <class T> ostream &operator<<(ostream &os, const vector<T> &container) {for (auto &u : container)os << u << " ";return os;} template<class T1, class T2> ostream& operator << (ostream& os, const pair<T1, T2>& p) {return os << p.first << " " << p.second;}template <class T> ostream &operator<<(ostream &os, set<T> const& con) {    for (auto &u : con)        os << u << " ";return os;} void pr() {} template <typename T, typename... args> void pr(T x, args... tail) {cout << x << " ";pr(tail...);}} using namespace fastio;

#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define F first
#define S second
#define pii pair < int , int >
#define _ <<" "<<
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
mt19937_64 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 2e5 + 5;
int cnt[N];
int t[N];

ll count_rectangles(vector < vector < int > > a){
    int n = a.size();
    int m = a[0].size();
    if (n <= 3){
        if (n <= 2) return 0;
        int start = 0;
        ll ans = 0;
        int i = 1;
        for (int i = 1; i + 1 < m; ++i){
            int mx = -1;
            for (int j = i; j + 1 < m; ++j){
                mx = max(mx, a[1][j]);
                if (a[1][j] >= a[0][j] || a[1][j] >= a[2][j]) break;
                if (mx >= a[1][i - 1] || mx >= a[1][j + 1]) continue;;
                ++ans;
            }
        }
        return ans;
    }
    bool group01 = 1;
    for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
        if (a[i][j] > 1) group01 = 0;
    if (group01){
        int ans = 0;
        int d[m] = {};
        for (int i = 1; i + 1 < n; ++i){
            for (int j = 1; j + 1 < m; ++j)
                if (a[i][j] == 1) d[j] = i;
            for (int j = 1; j + 1 < m; ++j){
                if (!a[i][j]){
                    int h = d[j];
                    int J = j;
                    while(J + 1 < m && !a[i][J]) ++J;
                    if (!a[i][J]) break;
                    bool good = 1;
                    for (int j1 = j; j1 <= J; ++j1)
                        if (!a[d[j]][j1] || !a[i + 1][j1]){
                            good = 0;
                            break;
                        }
                    for (int i1 = d[j] + 1; i1 <= i && good; ++i1)
                        if (!a[i1][j - 1] || !a[i1][J]){
                            good = 0;
                            break;
                        }
                    if (good)
                    for (int i1 = i; i1 <= i; ++i1)
                    for (int j1 = j; j1 <= J; ++j1)
                    if (a[i1][j]){
                        good = 0;
                        break;
                    }
                    if (good) ans++;
                    j = J;
                }
            }

        }
        return ans;
    }
    int ans = 0;
    for (int i = 1; i + 1 < n; ++i)
    for (int j = 1; j + 1 < m; ++j){
        if (a[i][j] >= a[i - 1][j] || a[i][j] >= a[i][j - 1]) continue;
        for (int i1 = i; i1 + 1 < n; ++i1)
        for (int j1 = j; j1 + 1 < m; ++j1){
            bool bad = 0;
            for (int k = i; k <= i1; ++k)
                if (a[k][j1] >= min(a[i - 1][j1], a[i1 + 1][j1]) ||
                    a[k][j1] >= a[k][j - 1]){
                        bad = 1;
                        break;
                    }
            if (bad) break;
            for (int I = i; I <= i1 && !bad; ++I)
            for (int J = j; J <= j1; ++J)
            if (a[I][J] >= min(a[I][j - 1], a[I][j1 + 1])){
                bad = 1;
                break;
            }
//            if (!bad)
//                cout<<i __ j __ i1 __ j1 << endl;
            ans += !bad;
        }
    }
    return ans;

}

#ifdef Estb_probitie
main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);

    int n, m;
    cin >> n >> m;
    vector < vector < int > > v;
    vector < int > a;
    for (int i = 0; i < n; ++i){
        for (int j = 0; j < m; ++j){\
            int x;
            cin >> x;
            a.pb(x);
        }
        v.pb(a);
        a.clear();
    }
    cout << count_rectangles(v);

}
#endif // Estb_probitie

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:62:13: warning: unused variable 'start' [-Wunused-variable]
         int start = 0;
             ^~~~~
rect.cpp:64:13: warning: unused variable 'i' [-Wunused-variable]
         int i = 1;
             ^
rect.cpp:88:25: warning: unused variable 'h' [-Wunused-variable]
                     int h = d[j];
                         ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28