oj.uz

Submission #768412

# Submission time Handle Problem Language Result Execution time Memory
768412 2023-06-28T05:52:11 Z marvinthang Rectangles (IOI19_rect) C++17
100 / 100
 1004 ms 225536 KB 
/*************************************
*    author: marvinthang             *
*    created: 28.06.2023 11:43:25    *
*************************************/

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

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template
// index from 0
template <class T = int>
    struct Fenwick {

        T *bit = nullptr;
        int n;

        Fenwick(int _n = 0) {
            resize(_n);
        }

        void reset(void) {
            fill(bit, bit + 1 + n, T(0));
        }

        void resize(int _n) {
            if (bit != nullptr) delete[] bit;
            n = _n;
            bit = new T[n + 1];
            reset();
        }

        void update(int i, T val) {
            assert(0 <= i);
            ++i;
            for (; i <= n; i += i & -i) bit[i] += val;
        }

        T get(int i) {
            if (i < 0) return T(0);
            ++i;
            i = min(i, n);
            T res(0);
            for (; i > 0; i -= i & -i)
                res += bit[i];
            return res;
        }

        int upper_bound(T val) {
            int res = 0;
            for (int i = __lg(n); i >= 0; --i) {
                if ((res | MASK(i)) <= n && val >= bit[res | MASK(i)]) {
                    res |= MASK(i);
                    val -= bit[res];
                }
            }
            return res;
        }

        int lower_bound(T val) {
            int res = 0;
            for (int i = __lg(n); i >= 0; --i) {
                if ((res | MASK(i)) <= n && val > bit[res | MASK(i)]) {
                    res |= MASK(i);
                    val -= bit[res];
                }
            }
            return res;
        }

    };


long long count_rectangles(vector <vector <int>> a) {
	int m = a.size(), n = a[0].size();
	vector <stack <int>> st_row(m - 1), st_col(n - 1);
	REP(i, m - 1) st_row[i].push(0);
	REP(i, n - 1) st_col[i].push(0);
	vector <vector <int>> cnt_row(n - 1, vector<int>(n - 1)), last_row(n - 1, vector<int>(n - 1)), cnt_col(m - 1, vector<int>(m - 1)), last_col(m - 1, vector<int>(m - 1));
	Fenwick <int> bit(m - 1);
	long long res = 0;
	REP(i, m - 1) REP(j, n - 1) {
		bool ok = true;
		vector <pair <int, int>> row, col;
		while (!st_row[i].empty()) {
			int pj = st_row[i].top();
			if (pj < j && ok) {
				if (last_row[pj + 1][j] < i - 1) cnt_row[pj + 1][j] = 0;
				++cnt_row[pj + 1][j];
				last_row[pj + 1][j] = i;
				row.emplace_back(j - pj, cnt_row[pj + 1][j]);
			}
			if (a[i][pj] > a[i][j + 1]) break;
			st_row[i].pop();
			ok &= a[i][pj] < a[i][j + 1];
		}
		st_row[i].push(j + 1);
		ok = true;
		while (!st_col[j].empty()) {
			int pi = st_col[j].top();
			if (pi < i && ok) {
				if (last_col[pi + 1][i] < j - 1) cnt_col[pi + 1][i] = 0;
				++cnt_col[pi + 1][i];
				last_col[pi + 1][i] = j;
				col.emplace_back(cnt_col[pi + 1][i], i - pi);
			}
			if (a[pi][j] > a[i + 1][j]) break;
			st_col[j].pop();
			ok &= a[pi][j] < a[i + 1][j];
		}
		st_col[j].push(i + 1);

		reverse(ALL(row));
		sort(col.rbegin(), col.rend());
		int i = 0;
		for (auto [a, b]: row) {
			while (i < col.size() && col[i].fi >= a) bit.update(col[i++].se, 1);
			res += bit.get(b);
		}
		while (i--) bit.update(col[i].se, -1);
	}
	return res;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:151:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |    while (i < col.size() && col[i].fi >= a) bit.update(col[i++].se, 1);
      |           ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 292 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 292 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 564 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 564 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 1 ms 292 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 4 ms 1748 KB Output is correct
31 Correct 4 ms 1876 KB Output is correct
32 Correct 4 ms 1876 KB Output is correct
33 Correct 3 ms 1620 KB Output is correct
34 Correct 6 ms 1692 KB Output is correct
35 Correct 7 ms 1848 KB Output is correct
36 Correct 6 ms 1748 KB Output is correct
37 Correct 6 ms 1748 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 564 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 4 ms 1748 KB Output is correct
26 Correct 4 ms 1876 KB Output is correct
27 Correct 4 ms 1876 KB Output is correct
28 Correct 3 ms 1620 KB Output is correct
29 Correct 6 ms 1692 KB Output is correct
30 Correct 7 ms 1848 KB Output is correct
31 Correct 6 ms 1748 KB Output is correct
32 Correct 6 ms 1748 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 1 ms 292 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 36 ms 14140 KB Output is correct
39 Correct 36 ms 14856 KB Output is correct
40 Correct 34 ms 14456 KB Output is correct
41 Correct 36 ms 15204 KB Output is correct
42 Correct 46 ms 15724 KB Output is correct
43 Correct 41 ms 15580 KB Output is correct
44 Correct 42 ms 15768 KB Output is correct
45 Correct 41 ms 14892 KB Output is correct
46 Correct 32 ms 13528 KB Output is correct
47 Correct 37 ms 13632 KB Output is correct
48 Correct 65 ms 13648 KB Output is correct
49 Correct 73 ms 13540 KB Output is correct
50 Correct 37 ms 8524 KB Output is correct
51 Correct 45 ms 8552 KB Output is correct
52 Correct 66 ms 13644 KB Output is correct
53 Correct 71 ms 13648 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 51204 KB Output is correct
2 Correct 14 ms 37204 KB Output is correct
3 Correct 24 ms 51116 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 22 ms 51128 KB Output is correct
6 Correct 20 ms 51168 KB Output is correct
7 Correct 21 ms 51164 KB Output is correct
8 Correct 21 ms 51184 KB Output is correct
9 Correct 20 ms 51156 KB Output is correct
10 Correct 19 ms 51012 KB Output is correct
11 Correct 20 ms 51124 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 198 ms 80080 KB Output is correct
8 Correct 411 ms 150904 KB Output is correct
9 Correct 416 ms 151800 KB Output is correct
10 Correct 415 ms 151612 KB Output is correct
11 Correct 112 ms 88652 KB Output is correct
12 Correct 192 ms 142600 KB Output is correct
13 Correct 207 ms 151620 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 300 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 564 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 4 ms 1748 KB Output is correct
26 Correct 4 ms 1876 KB Output is correct
27 Correct 4 ms 1876 KB Output is correct
28 Correct 3 ms 1620 KB Output is correct
29 Correct 6 ms 1692 KB Output is correct
30 Correct 7 ms 1848 KB Output is correct
31 Correct 6 ms 1748 KB Output is correct
32 Correct 6 ms 1748 KB Output is correct
33 Correct 36 ms 14140 KB Output is correct
34 Correct 36 ms 14856 KB Output is correct
35 Correct 34 ms 14456 KB Output is correct
36 Correct 36 ms 15204 KB Output is correct
37 Correct 46 ms 15724 KB Output is correct
38 Correct 41 ms 15580 KB Output is correct
39 Correct 42 ms 15768 KB Output is correct
40 Correct 41 ms 14892 KB Output is correct
41 Correct 32 ms 13528 KB Output is correct
42 Correct 37 ms 13632 KB Output is correct
43 Correct 65 ms 13648 KB Output is correct
44 Correct 73 ms 13540 KB Output is correct
45 Correct 37 ms 8524 KB Output is correct
46 Correct 45 ms 8552 KB Output is correct
47 Correct 66 ms 13644 KB Output is correct
48 Correct 71 ms 13648 KB Output is correct
49 Correct 19 ms 51204 KB Output is correct
50 Correct 14 ms 37204 KB Output is correct
51 Correct 24 ms 51116 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 22 ms 51128 KB Output is correct
54 Correct 20 ms 51168 KB Output is correct
55 Correct 21 ms 51164 KB Output is correct
56 Correct 21 ms 51184 KB Output is correct
57 Correct 20 ms 51156 KB Output is correct
58 Correct 19 ms 51012 KB Output is correct
59 Correct 20 ms 51124 KB Output is correct
60 Correct 1 ms 212 KB Output is correct
61 Correct 198 ms 80080 KB Output is correct
62 Correct 411 ms 150904 KB Output is correct
63 Correct 416 ms 151800 KB Output is correct
64 Correct 415 ms 151612 KB Output is correct
65 Correct 112 ms 88652 KB Output is correct
66 Correct 192 ms 142600 KB Output is correct
67 Correct 207 ms 151620 KB Output is correct
68 Correct 1 ms 212 KB Output is correct
69 Correct 0 ms 212 KB Output is correct
70 Correct 1 ms 292 KB Output is correct
71 Correct 0 ms 340 KB Output is correct
72 Correct 0 ms 212 KB Output is correct
73 Correct 529 ms 158584 KB Output is correct
74 Correct 538 ms 168356 KB Output is correct
75 Correct 622 ms 164092 KB Output is correct
76 Correct 576 ms 175996 KB Output is correct
77 Correct 765 ms 177740 KB Output is correct
78 Correct 570 ms 100172 KB Output is correct
79 Correct 612 ms 102788 KB Output is correct
80 Correct 924 ms 151012 KB Output is correct
81 Correct 607 ms 99304 KB Output is correct
82 Correct 805 ms 123260 KB Output is correct
83 Correct 1004 ms 151132 KB Output is correct
84 Correct 556 ms 99300 KB Output is correct
85 Correct 965 ms 151028 KB Output is correct
86 Correct 940 ms 146892 KB Output is correct
87 Correct 421 ms 115160 KB Output is correct
88 Correct 769 ms 225236 KB Output is correct
89 Correct 721 ms 225432 KB Output is correct
90 Correct 722 ms 225536 KB Output is correct