oj.uz

Submission #1038476

# Submission time Handle Problem Language Result Execution time Memory
1038476 2024-07-29T20:39:19 Z c2zi6 Rectangles (IOI19_rect) C++14
100 / 100
 1360 ms 444932 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "rect.h"

int gu[3000][3000], gd[3000][3000], gl[3000][3000], gr[3000][3000];
int lu[3000][3000], ru[3000][3000], ul[3000][3000], dl[3000][3000];

VL rect;
void check(int x1, int x2, int y1, int y2) {
    if (x2 < x1 || y2 < y1) return;
    if ((gu[x2+1][y2] == x1-1 && ul[x2+1][y2] <= y1) || (gd[x1-1][y2] == x2+1 && dl[x1-1][y2] <= y1)); else return;
    if ((gr[x2][y1-1] == y2+1 && ru[x2][y1-1] <= x1) || (gl[x2][y2+1] == y1-1 && lu[x2][y2+1] <= x1)); else return;
    rect.pb(1ll*x1*3000*3000*3000 + 1ll*x2*3000*3000 + 1ll*y1*3000 + 1ll*y2);
}

ll count_rectangles(VVI a) {
    int n = a.size();
    int m = a[0].size();
    rep(i, n) {
        stack<int> st;
        replr(j, 0, m-1) {
            while (st.size() && a[i][st.top()] < a[i][j]) st.pop();
            gl[i][j] = (st.size() ? st.top() : -1);
            st.push(j);
        }
        st = stack<int>();
        reprl(j, m-1, 0) {
            while (st.size() && a[i][st.top()] < a[i][j]) st.pop();
            gr[i][j] = (st.size() ? st.top() : -1);
            st.push(j);
        }
    }
    rep(j, m) {
        stack<int> st;
        replr(i, 0, n-1) {
            while (st.size() && a[st.top()][j] < a[i][j]) st.pop();
            gu[i][j] = (st.size() ? st.top() : -1);
            st.push(i);
        }
        st = stack<int>();
        reprl(i, n-1, 0) {
            while (st.size() && a[st.top()][j] < a[i][j]) st.pop();
            gd[i][j] = (st.size() ? st.top() : -1);
            st.push(i);
        }
    }
    rep(i, n) {
        rep(j, m) {
            if (~gl[i][j]) {
                if (i && gl[i-1][j] == gl[i][j]) lu[i][j] = lu[i-1][j];
                else if (i && gr[i-1][gl[i][j]] == j) lu[i][j] = ru[i-1][gl[i][j]];
                else lu[i][j] = i;
            }
            if (~gr[i][j]) {
                if (i && gr[i-1][j] == gr[i][j]) ru[i][j] = ru[i-1][j];
                else if (i && gl[i-1][gr[i][j]] == j) ru[i][j] = lu[i-1][gr[i][j]];
                else ru[i][j] = i;
            }
        }
    }
    rep(j, m) {
        rep(i, n) {
            if (~gu[i][j]) {
                if (j && gu[i][j-1] == gu[i][j]) ul[i][j] = ul[i][j-1];
                else if (j && gd[gu[i][j]][j-1] == i) ul[i][j] = dl[gu[i][j]][j-1];
                else ul[i][j] = j;
            }
            if (~gd[i][j]) {
                if (j && gd[i][j-1] == gd[i][j]) dl[i][j] = dl[i][j-1];
                else if (j && gu[gd[i][j]][j-1] == i) dl[i][j] = ul[gd[i][j]][j-1];
                else dl[i][j] = j;
            } else dl[i][j] = -1;
        }
    }
    rect.clear();
    replr(i, 1, n-2) replr(j, 1, m-2) {
        if (~gd[i-1][j] && ~gr[i][j-1]) check(i, gd[i-1][j]-1, j, gr[i][j-1]-1);
        if (~gd[i-1][j] && ~gl[i][j+1]) check(i, gd[i-1][j]-1, gl[i][j+1]+1, j);
        if (~gu[i+1][j] && ~gr[i][j-1]) check(gu[i+1][j]+1, i, j, gr[i][j-1]-1);
        if (~gu[i+1][j] && ~gl[i][j+1]) check(gu[i+1][j]+1, i, gl[i][j+1]+1, j);
        if (!~gr[i][j-1]) continue;
        int nextj = gr[i][j-1]-1;
        if (~gu[i+1][nextj]) check(gu[i+1][nextj]+1, i, j, nextj);
        if (~gd[i-1][nextj]) check(i, gd[i-1][nextj]-1, j, nextj);
    }
    ll ans = 0;
    if (rect.size()) {
        sort(all(rect));
        ans = 1;
        rep(i, rect.size()-1) ans += (rect[i] != rect[i+1]);
    }
    return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 18776 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 2 ms 18780 KB Output is correct
8 Correct 1 ms 14684 KB Output is correct
9 Correct 2 ms 18780 KB Output is correct
10 Correct 2 ms 18780 KB Output is correct
11 Correct 2 ms 18780 KB Output is correct
12 Correct 2 ms 18780 KB Output is correct
13 Correct 1 ms 8536 KB Output is correct
14 Correct 2 ms 14680 KB Output is correct
15 Correct 1 ms 14804 KB Output is correct
16 Correct 1 ms 14684 KB Output is correct
17 Correct 1 ms 8636 KB Output is correct
18 Correct 1 ms 12636 KB Output is correct
19 Correct 2 ms 18780 KB Output is correct
20 Correct 2 ms 18780 KB Output is correct
21 Correct 1 ms 14684 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 18776 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 2 ms 18780 KB Output is correct
8 Correct 1 ms 14684 KB Output is correct
9 Correct 2 ms 18780 KB Output is correct
10 Correct 2 ms 18780 KB Output is correct
11 Correct 2 ms 18780 KB Output is correct
12 Correct 2 ms 18780 KB Output is correct
13 Correct 1 ms 8536 KB Output is correct
14 Correct 2 ms 14680 KB Output is correct
15 Correct 1 ms 14804 KB Output is correct
16 Correct 1 ms 14684 KB Output is correct
17 Correct 1 ms 8636 KB Output is correct
18 Correct 1 ms 12636 KB Output is correct
19 Correct 2 ms 18780 KB Output is correct
20 Correct 2 ms 18780 KB Output is correct
21 Correct 1 ms 14684 KB Output is correct
22 Correct 3 ms 23388 KB Output is correct
23 Correct 3 ms 23388 KB Output is correct
24 Correct 3 ms 23388 KB Output is correct
25 Correct 3 ms 23132 KB Output is correct
26 Correct 3 ms 23016 KB Output is correct
27 Correct 3 ms 23132 KB Output is correct
28 Correct 3 ms 22980 KB Output is correct
29 Correct 2 ms 23132 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 18776 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 2 ms 18780 KB Output is correct
8 Correct 1 ms 14684 KB Output is correct
9 Correct 2 ms 18780 KB Output is correct
10 Correct 2 ms 18780 KB Output is correct
11 Correct 2 ms 18780 KB Output is correct
12 Correct 2 ms 18780 KB Output is correct
13 Correct 1 ms 8536 KB Output is correct
14 Correct 2 ms 14680 KB Output is correct
15 Correct 1 ms 14804 KB Output is correct
16 Correct 1 ms 14684 KB Output is correct
17 Correct 3 ms 23388 KB Output is correct
18 Correct 3 ms 23388 KB Output is correct
19 Correct 3 ms 23388 KB Output is correct
20 Correct 3 ms 23132 KB Output is correct
21 Correct 3 ms 23016 KB Output is correct
22 Correct 3 ms 23132 KB Output is correct
23 Correct 3 ms 22980 KB Output is correct
24 Correct 2 ms 23132 KB Output is correct
25 Correct 1 ms 8636 KB Output is correct
26 Correct 1 ms 12636 KB Output is correct
27 Correct 2 ms 18780 KB Output is correct
28 Correct 2 ms 18780 KB Output is correct
29 Correct 1 ms 14684 KB Output is correct
30 Correct 8 ms 37072 KB Output is correct
31 Correct 8 ms 36996 KB Output is correct
32 Correct 8 ms 37076 KB Output is correct
33 Correct 6 ms 35932 KB Output is correct
34 Correct 8 ms 36184 KB Output is correct
35 Correct 8 ms 36312 KB Output is correct
36 Correct 8 ms 36168 KB Output is correct
37 Correct 8 ms 36404 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 18776 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 2 ms 18780 KB Output is correct
8 Correct 1 ms 14684 KB Output is correct
9 Correct 2 ms 18780 KB Output is correct
10 Correct 2 ms 18780 KB Output is correct
11 Correct 2 ms 18780 KB Output is correct
12 Correct 2 ms 18780 KB Output is correct
13 Correct 1 ms 8536 KB Output is correct
14 Correct 2 ms 14680 KB Output is correct
15 Correct 1 ms 14804 KB Output is correct
16 Correct 1 ms 14684 KB Output is correct
17 Correct 3 ms 23388 KB Output is correct
18 Correct 3 ms 23388 KB Output is correct
19 Correct 3 ms 23388 KB Output is correct
20 Correct 3 ms 23132 KB Output is correct
21 Correct 3 ms 23016 KB Output is correct
22 Correct 3 ms 23132 KB Output is correct
23 Correct 3 ms 22980 KB Output is correct
24 Correct 2 ms 23132 KB Output is correct
25 Correct 8 ms 37072 KB Output is correct
26 Correct 8 ms 36996 KB Output is correct
27 Correct 8 ms 37076 KB Output is correct
28 Correct 6 ms 35932 KB Output is correct
29 Correct 8 ms 36184 KB Output is correct
30 Correct 8 ms 36312 KB Output is correct
31 Correct 8 ms 36168 KB Output is correct
32 Correct 8 ms 36404 KB Output is correct
33 Correct 1 ms 8636 KB Output is correct
34 Correct 1 ms 12636 KB Output is correct
35 Correct 2 ms 18780 KB Output is correct
36 Correct 2 ms 18780 KB Output is correct
37 Correct 1 ms 14684 KB Output is correct
38 Correct 34 ms 82036 KB Output is correct
39 Correct 34 ms 83196 KB Output is correct
40 Correct 42 ms 83192 KB Output is correct
41 Correct 35 ms 82408 KB Output is correct
42 Correct 81 ms 90812 KB Output is correct
43 Correct 86 ms 91584 KB Output is correct
44 Correct 83 ms 90996 KB Output is correct
45 Correct 87 ms 88256 KB Output is correct
46 Correct 48 ms 82488 KB Output is correct
47 Correct 55 ms 84424 KB Output is correct
48 Correct 69 ms 83652 KB Output is correct
49 Correct 76 ms 85580 KB Output is correct
50 Correct 47 ms 80592 KB Output is correct
51 Correct 41 ms 51916 KB Output is correct
52 Correct 70 ms 84168 KB Output is correct
53 Correct 73 ms 85700 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14940 KB Output is correct
2 Correct 2 ms 14940 KB Output is correct
3 Correct 2 ms 14684 KB Output is correct
4 Correct 1 ms 10840 KB Output is correct
5 Correct 2 ms 14776 KB Output is correct
6 Correct 2 ms 14940 KB Output is correct
7 Correct 2 ms 14940 KB Output is correct
8 Correct 2 ms 14940 KB Output is correct
9 Correct 2 ms 14940 KB Output is correct
10 Correct 1 ms 12636 KB Output is correct
11 Correct 2 ms 14684 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8636 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 1 ms 14684 KB Output is correct
6 Correct 1 ms 14684 KB Output is correct
7 Correct 256 ms 159472 KB Output is correct
8 Correct 569 ms 309176 KB Output is correct
9 Correct 665 ms 312752 KB Output is correct
10 Correct 572 ms 312232 KB Output is correct
11 Correct 144 ms 152856 KB Output is correct
12 Correct 324 ms 292252 KB Output is correct
13 Correct 349 ms 295764 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 2 ms 18776 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 18780 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 2 ms 18780 KB Output is correct
8 Correct 1 ms 14684 KB Output is correct
9 Correct 2 ms 18780 KB Output is correct
10 Correct 2 ms 18780 KB Output is correct
11 Correct 2 ms 18780 KB Output is correct
12 Correct 2 ms 18780 KB Output is correct
13 Correct 1 ms 8536 KB Output is correct
14 Correct 2 ms 14680 KB Output is correct
15 Correct 1 ms 14804 KB Output is correct
16 Correct 1 ms 14684 KB Output is correct
17 Correct 3 ms 23388 KB Output is correct
18 Correct 3 ms 23388 KB Output is correct
19 Correct 3 ms 23388 KB Output is correct
20 Correct 3 ms 23132 KB Output is correct
21 Correct 3 ms 23016 KB Output is correct
22 Correct 3 ms 23132 KB Output is correct
23 Correct 3 ms 22980 KB Output is correct
24 Correct 2 ms 23132 KB Output is correct
25 Correct 8 ms 37072 KB Output is correct
26 Correct 8 ms 36996 KB Output is correct
27 Correct 8 ms 37076 KB Output is correct
28 Correct 6 ms 35932 KB Output is correct
29 Correct 8 ms 36184 KB Output is correct
30 Correct 8 ms 36312 KB Output is correct
31 Correct 8 ms 36168 KB Output is correct
32 Correct 8 ms 36404 KB Output is correct
33 Correct 34 ms 82036 KB Output is correct
34 Correct 34 ms 83196 KB Output is correct
35 Correct 42 ms 83192 KB Output is correct
36 Correct 35 ms 82408 KB Output is correct
37 Correct 81 ms 90812 KB Output is correct
38 Correct 86 ms 91584 KB Output is correct
39 Correct 83 ms 90996 KB Output is correct
40 Correct 87 ms 88256 KB Output is correct
41 Correct 48 ms 82488 KB Output is correct
42 Correct 55 ms 84424 KB Output is correct
43 Correct 69 ms 83652 KB Output is correct
44 Correct 76 ms 85580 KB Output is correct
45 Correct 47 ms 80592 KB Output is correct
46 Correct 41 ms 51916 KB Output is correct
47 Correct 70 ms 84168 KB Output is correct
48 Correct 73 ms 85700 KB Output is correct
49 Correct 2 ms 14940 KB Output is correct
50 Correct 2 ms 14940 KB Output is correct
51 Correct 2 ms 14684 KB Output is correct
52 Correct 1 ms 10840 KB Output is correct
53 Correct 2 ms 14776 KB Output is correct
54 Correct 2 ms 14940 KB Output is correct
55 Correct 2 ms 14940 KB Output is correct
56 Correct 2 ms 14940 KB Output is correct
57 Correct 2 ms 14940 KB Output is correct
58 Correct 1 ms 12636 KB Output is correct
59 Correct 2 ms 14684 KB Output is correct
60 Correct 1 ms 14684 KB Output is correct
61 Correct 256 ms 159472 KB Output is correct
62 Correct 569 ms 309176 KB Output is correct
63 Correct 665 ms 312752 KB Output is correct
64 Correct 572 ms 312232 KB Output is correct
65 Correct 144 ms 152856 KB Output is correct
66 Correct 324 ms 292252 KB Output is correct
67 Correct 349 ms 295764 KB Output is correct
68 Correct 1 ms 8636 KB Output is correct
69 Correct 1 ms 12636 KB Output is correct
70 Correct 2 ms 18780 KB Output is correct
71 Correct 2 ms 18780 KB Output is correct
72 Correct 1 ms 14684 KB Output is correct
73 Correct 453 ms 297604 KB Output is correct
74 Correct 429 ms 297612 KB Output is correct
75 Correct 454 ms 305300 KB Output is correct
76 Correct 442 ms 305232 KB Output is correct
77 Correct 1226 ms 444852 KB Output is correct
78 Correct 547 ms 201996 KB Output is correct
79 Correct 590 ms 277008 KB Output is correct
80 Correct 925 ms 333716 KB Output is correct
81 Correct 575 ms 209428 KB Output is correct
82 Correct 777 ms 332264 KB Output is correct
83 Correct 994 ms 346456 KB Output is correct
84 Correct 533 ms 205916 KB Output is correct
85 Correct 987 ms 346584 KB Output is correct
86 Correct 1016 ms 337600 KB Output is correct
87 Correct 711 ms 323692 KB Output is correct
88 Correct 1257 ms 420940 KB Output is correct
89 Correct 1314 ms 444932 KB Output is correct
90 Correct 1360 ms 444904 KB Output is correct