oj.uz

Submission #278514

# Submission time Handle Problem Language Result Execution time Memory
278514 2020-08-21T13:30:26 Z Kastanda Rectangles (IOI19_rect) C++14
100 / 100
 3832 ms 431624 KB 
// M
#include<bits/stdc++.h>
#include "rect.h"
using namespace std;
const int N = 2505, MXN = N * N, LG = 13;
int L[N][N], R[N][N], D[N][N], U[N][N], RMQ[LG][N], Log[N];
bool Cant[MXN];
vector < int > qL[N], qR[N], qU[N], qD[N];
vector < int > Gen(vector < int > A, int w = 0)
{
        int k = (int)A.size();
        vector < int > Rs(k);
        for (int i = 0; i < k; i ++)
        {
                Rs[i] = i - 1;
                while (Rs[i] >= 0 && A[Rs[i]] < A[i] + w)
                        Rs[i] = Rs[Rs[i]];
        }
        return Rs;
}
long long count_rectangles(vector < vector < int > > A)
{
        int n = (int)A.size();
        int m = (int)A[0].size();

        for (int i = 0; i < n; i ++)
        {
                vector < int > temp, res;
                for (int j = 0; j < m; j ++)
                        temp.push_back(A[i][j]);
                res = Gen(temp, 1);
                for (int j = 0; j < m; j ++)
                        L[i][j] = res[j];
                reverse(temp.begin(), temp.end());
                res = Gen(temp, 1);
                for (int j = 0; j < m; j ++)
                        R[i][j] = m - res[m - j - 1] - 1;
        }

        for (int j = 0; j < m; j ++)
        {
                vector < int > temp, res;
                for (int i = 0; i < n; i ++)
                        temp.push_back(A[i][j]);
                res = Gen(temp, 1);
                for (int i = 0; i < n; i ++)
                        U[i][j] = res[i];
                reverse(temp.begin(), temp.end());
                res = Gen(temp, 1);
                for (int i = 0; i < n; i ++)
                        D[i][j] = n - res[n - i - 1] - 1;
        }

        vector < tuple < int , int , int , int > > Cands;
        for (int i = 0; i < n; i ++)
                for (int j = 0; j < m; j ++)
                        if (L[i][j] >= 0 && R[i][j] < m && U[i][j] >= 0 && D[i][j] < n)
                                Cands.push_back(make_tuple(U[i][j], D[i][j], L[i][j], R[i][j]));

        for (int i = 0; i < n; i ++)
        {
                vector < int > temp, res;
                for (int j = 0; j < m; j ++)
                        temp.push_back(A[i][j]);
                res = Gen(temp, 0);
                for (int j = 0; j < m; j ++)
                        L[i][j] = res[j];
                reverse(temp.begin(), temp.end());
                res = Gen(temp, 0);
                for (int j = 0; j < m; j ++)
                        R[i][j] = m - res[m - j - 1] - 1;
        }

        for (int j = 0; j < m; j ++)
        {
                vector < int > temp, res;
                for (int i = 0; i < n; i ++)
                        temp.push_back(A[i][j]);
                res = Gen(temp, 0);
                for (int i = 0; i < n; i ++)
                        U[i][j] = res[i];
                reverse(temp.begin(), temp.end());
                res = Gen(temp, 0);
                for (int i = 0; i < n; i ++)
                        D[i][j] = n - res[n - i - 1] - 1;
        }

        for (int i = 0; i < n; i ++)
                for (int j = 0; j < m; j ++)
                {
                        L[i][j] = j - L[i][j];
                        R[i][j] = R[i][j] - j;
                        U[i][j] = i - U[i][j];
                        D[i][j] = D[i][j] - i;
                }

        sort(Cands.begin(), Cands.end());
        Cands.resize(unique(Cands.begin(), Cands.end()) - Cands.begin());
        for (int i = 0; i < (int)Cands.size(); i ++)
        {
                int a, b, c, d;
                tie(a, b, c, d) = Cands[i];
                assert(a + 1 < b && c + 1 < d);
                qL[d].push_back(i);
                qR[c].push_back(i);
                qU[b].push_back(i);
                qD[a].push_back(i);
        }

        auto GetMin = [&](int l, int r) {
                int lg = Log[r - l];
                return min(RMQ[lg][l], RMQ[lg][r - (1 << lg)]);
        };

        for (int i = 2; i < N; i ++)
                Log[i] = Log[i >> 1] + 1;

        for (int i = 0; i < n; i ++)
        {
                for (int j = 0; j < m; j ++)
                        RMQ[0][j] = U[i][j];
                for (int lg = 1; lg < LG; lg ++)
                        for (int j = 0; j + (1 << lg) <= m; j ++)
                                RMQ[lg][j] = min(RMQ[lg - 1][j], RMQ[lg - 1][j + (1 << (lg - 1))]);
                for (int id : qU[i])
                {
                        int a, b, c, d;
                        tie(a, b, c, d) = Cands[id];
                        if (GetMin(c + 1, d) < b - a)
                                Cant[id] = 1;
                }

                for (int j = 0; j < m; j ++)
                        RMQ[0][j] = D[i][j];
                for (int lg = 1; lg < LG; lg ++)
                        for (int j = 0; j + (1 << lg) <= m; j ++)
                                RMQ[lg][j] = min(RMQ[lg - 1][j], RMQ[lg - 1][j + (1 << (lg - 1))]);
                for (int id : qD[i])
                {
                        int a, b, c, d;
                        tie(a, b, c, d) = Cands[id];
                        if (GetMin(c + 1, d) < b - a)
                                Cant[id] = 1;
                }
        }

        for (int j = 0; j < m; j ++)
        {
                for (int i = 0; i < n; i ++)
                        RMQ[0][i] = L[i][j];
                for (int lg = 1; lg < LG; lg ++)
                        for (int i = 0; i + (1 << lg) <= n; i ++)
                                RMQ[lg][i] = min(RMQ[lg - 1][i], RMQ[lg - 1][i + (1 << (lg - 1))]);
                for (int id : qL[j])
                {
                        int a, b, c, d;
                        tie(a, b, c, d) = Cands[id];
                        if (GetMin(a + 1, b) < d - c)
                                Cant[id] = 1;
                }

                for (int i = 0; i < n; i ++)
                        RMQ[0][i] = R[i][j];
                for (int lg = 1; lg < LG; lg ++)
                        for (int i = 0; i + (1 << lg) <= n; i ++)
                                RMQ[lg][i] = min(RMQ[lg - 1][i], RMQ[lg - 1][i + (1 << (lg - 1))]);
                for (int id : qR[j])
                {
                        int a, b, c, d;
                        tie(a, b, c, d) = Cands[id];
                        if (GetMin(a + 1, b) < d - c)
                                Cant[id] = 1;
                }
        }

        int Cnt = 0;
        for (int i = 0; i < (int)Cands.size(); i ++)
                if (!Cant[i])
                        Cnt ++;
        return Cnt;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 1 ms 1152 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 1152 KB Output is correct
10 Correct 1 ms 1152 KB Output is correct
11 Correct 1 ms 1152 KB Output is correct
12 Correct 1 ms 1152 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 1 ms 768 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 1 ms 640 KB Output is correct
17 Correct 3 ms 2304 KB Output is correct
18 Correct 3 ms 2304 KB Output is correct
19 Correct 3 ms 2304 KB Output is correct
20 Correct 4 ms 2304 KB Output is correct
21 Correct 4 ms 2304 KB Output is correct
22 Correct 4 ms 2304 KB Output is correct
23 Correct 4 ms 2304 KB Output is correct
24 Correct 3 ms 2048 KB Output is correct
25 Correct 1 ms 640 KB Output is correct
26 Correct 1 ms 640 KB Output is correct
27 Correct 2 ms 1152 KB Output is correct
28 Correct 1 ms 1152 KB Output is correct
29 Correct 1 ms 768 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 1 ms 1152 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 1152 KB Output is correct
10 Correct 1 ms 1152 KB Output is correct
11 Correct 1 ms 1152 KB Output is correct
12 Correct 1 ms 1152 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 1 ms 768 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 1 ms 640 KB Output is correct
17 Correct 3 ms 2304 KB Output is correct
18 Correct 3 ms 2304 KB Output is correct
19 Correct 3 ms 2304 KB Output is correct
20 Correct 4 ms 2304 KB Output is correct
21 Correct 4 ms 2304 KB Output is correct
22 Correct 4 ms 2304 KB Output is correct
23 Correct 4 ms 2304 KB Output is correct
24 Correct 3 ms 2048 KB Output is correct
25 Correct 14 ms 6520 KB Output is correct
26 Correct 13 ms 6520 KB Output is correct
27 Correct 13 ms 6648 KB Output is correct
28 Correct 17 ms 5756 KB Output is correct
29 Correct 19 ms 6392 KB Output is correct
30 Correct 20 ms 6520 KB Output is correct
31 Correct 19 ms 6512 KB Output is correct
32 Correct 19 ms 6388 KB Output is correct
33 Correct 1 ms 640 KB Output is correct
34 Correct 1 ms 640 KB Output is correct
35 Correct 2 ms 1152 KB Output is correct
36 Correct 1 ms 1152 KB Output is correct
37 Correct 1 ms 768 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 1 ms 1152 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 1152 KB Output is correct
10 Correct 1 ms 1152 KB Output is correct
11 Correct 1 ms 1152 KB Output is correct
12 Correct 1 ms 1152 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 1 ms 768 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 1 ms 640 KB Output is correct
17 Correct 3 ms 2304 KB Output is correct
18 Correct 3 ms 2304 KB Output is correct
19 Correct 3 ms 2304 KB Output is correct
20 Correct 4 ms 2304 KB Output is correct
21 Correct 4 ms 2304 KB Output is correct
22 Correct 4 ms 2304 KB Output is correct
23 Correct 4 ms 2304 KB Output is correct
24 Correct 3 ms 2048 KB Output is correct
25 Correct 14 ms 6520 KB Output is correct
26 Correct 13 ms 6520 KB Output is correct
27 Correct 13 ms 6648 KB Output is correct
28 Correct 17 ms 5756 KB Output is correct
29 Correct 19 ms 6392 KB Output is correct
30 Correct 20 ms 6520 KB Output is correct
31 Correct 19 ms 6512 KB Output is correct
32 Correct 19 ms 6388 KB Output is correct
33 Correct 109 ms 26616 KB Output is correct
34 Correct 107 ms 26724 KB Output is correct
35 Correct 107 ms 26724 KB Output is correct
36 Correct 110 ms 26616 KB Output is correct
37 Correct 180 ms 43856 KB Output is correct
38 Correct 195 ms 43920 KB Output is correct
39 Correct 182 ms 44112 KB Output is correct
40 Correct 172 ms 41556 KB Output is correct
41 Correct 179 ms 34192 KB Output is correct
42 Correct 203 ms 35796 KB Output is correct
43 Correct 268 ms 45136 KB Output is correct
44 Correct 272 ms 47184 KB Output is correct
45 Correct 132 ms 29152 KB Output is correct
46 Correct 118 ms 23776 KB Output is correct
47 Correct 270 ms 44244 KB Output is correct
48 Correct 283 ms 45520 KB Output is correct
49 Correct 1 ms 640 KB Output is correct
50 Correct 1 ms 640 KB Output is correct
51 Correct 2 ms 1152 KB Output is correct
52 Correct 1 ms 1152 KB Output is correct
53 Correct 1 ms 768 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1071 ms 121128 KB Output is correct
3 Correct 2299 ms 269608 KB Output is correct
4 Correct 2302 ms 275284 KB Output is correct
5 Correct 2385 ms 271844 KB Output is correct
6 Correct 609 ms 79480 KB Output is correct
7 Correct 1169 ms 156408 KB Output is correct
8 Correct 1257 ms 160120 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 2 ms 1152 KB Output is correct
12 Correct 1 ms 1152 KB Output is correct
13 Correct 1 ms 768 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 1 ms 1152 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 1152 KB Output is correct
10 Correct 1 ms 1152 KB Output is correct
11 Correct 1 ms 1152 KB Output is correct
12 Correct 1 ms 1152 KB Output is correct
13 Correct 1 ms 640 KB Output is correct
14 Correct 1 ms 768 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Correct 1 ms 640 KB Output is correct
17 Correct 3 ms 2304 KB Output is correct
18 Correct 3 ms 2304 KB Output is correct
19 Correct 3 ms 2304 KB Output is correct
20 Correct 4 ms 2304 KB Output is correct
21 Correct 4 ms 2304 KB Output is correct
22 Correct 4 ms 2304 KB Output is correct
23 Correct 4 ms 2304 KB Output is correct
24 Correct 3 ms 2048 KB Output is correct
25 Correct 14 ms 6520 KB Output is correct
26 Correct 13 ms 6520 KB Output is correct
27 Correct 13 ms 6648 KB Output is correct
28 Correct 17 ms 5756 KB Output is correct
29 Correct 19 ms 6392 KB Output is correct
30 Correct 20 ms 6520 KB Output is correct
31 Correct 19 ms 6512 KB Output is correct
32 Correct 19 ms 6388 KB Output is correct
33 Correct 109 ms 26616 KB Output is correct
34 Correct 107 ms 26724 KB Output is correct
35 Correct 107 ms 26724 KB Output is correct
36 Correct 110 ms 26616 KB Output is correct
37 Correct 180 ms 43856 KB Output is correct
38 Correct 195 ms 43920 KB Output is correct
39 Correct 182 ms 44112 KB Output is correct
40 Correct 172 ms 41556 KB Output is correct
41 Correct 179 ms 34192 KB Output is correct
42 Correct 203 ms 35796 KB Output is correct
43 Correct 268 ms 45136 KB Output is correct
44 Correct 272 ms 47184 KB Output is correct
45 Correct 132 ms 29152 KB Output is correct
46 Correct 118 ms 23776 KB Output is correct
47 Correct 270 ms 44244 KB Output is correct
48 Correct 283 ms 45520 KB Output is correct
49 Correct 3 ms 1024 KB Output is correct
50 Correct 3 ms 1024 KB Output is correct
51 Correct 3 ms 896 KB Output is correct
52 Correct 1 ms 640 KB Output is correct
53 Correct 4 ms 1024 KB Output is correct
54 Correct 4 ms 1024 KB Output is correct
55 Correct 4 ms 1024 KB Output is correct
56 Correct 4 ms 1024 KB Output is correct
57 Correct 5 ms 1024 KB Output is correct
58 Correct 2 ms 896 KB Output is correct
59 Correct 3 ms 896 KB Output is correct
60 Correct 1 ms 768 KB Output is correct
61 Correct 1071 ms 121128 KB Output is correct
62 Correct 2299 ms 269608 KB Output is correct
63 Correct 2302 ms 275284 KB Output is correct
64 Correct 2385 ms 271844 KB Output is correct
65 Correct 609 ms 79480 KB Output is correct
66 Correct 1169 ms 156408 KB Output is correct
67 Correct 1257 ms 160120 KB Output is correct
68 Correct 1415 ms 161144 KB Output is correct
69 Correct 1416 ms 161904 KB Output is correct
70 Correct 1428 ms 174840 KB Output is correct
71 Correct 1418 ms 174968 KB Output is correct
72 Correct 2388 ms 400068 KB Output is correct
73 Correct 2090 ms 249432 KB Output is correct
74 Correct 2252 ms 305708 KB Output is correct
75 Correct 3617 ms 414916 KB Output is correct
76 Correct 2188 ms 265016 KB Output is correct
77 Correct 2959 ms 364480 KB Output is correct
78 Correct 3832 ms 431624 KB Output is correct
79 Correct 2011 ms 245464 KB Output is correct
80 Correct 3438 ms 397800 KB Output is correct
81 Correct 3305 ms 380088 KB Output is correct
82 Correct 1398 ms 289236 KB Output is correct
83 Correct 2343 ms 400732 KB Output is correct
84 Correct 2374 ms 400900 KB Output is correct
85 Correct 2426 ms 401040 KB Output is correct
86 Correct 1 ms 640 KB Output is correct
87 Correct 1 ms 640 KB Output is correct
88 Correct 2 ms 1152 KB Output is correct
89 Correct 1 ms 1152 KB Output is correct
90 Correct 1 ms 768 KB Output is correct