oj.uz

Submission #260080

# Submission time Handle Problem Language Result Execution time Memory
260080 2020-08-09T09:04:07 Z dandrozavr Rectangles (IOI19_rect) C++14
23 / 100
 194 ms 61688 KB 
/*
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 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 = d[j] + 1; i1 <= i; ++i1)
                    for (int j1 = j; j1 < J; ++j1)
                    if (a[i1][j1]){
                        good = 0;
                        break;
                    }
                    if (good) ans++;
                    j = J;
                }
            }

        }
        return ans;
    }
    return 0;
    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

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;
             ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 83 ms 22784 KB Output is correct
3 Correct 194 ms 61396 KB Output is correct
4 Correct 186 ms 61688 KB Output is correct
5 Correct 187 ms 61688 KB Output is correct
6 Correct 47 ms 30584 KB Output is correct
7 Correct 101 ms 57848 KB Output is correct
8 Correct 106 ms 61688 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -