oj.uz

답안 #143520

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143520 2019-08-14T13:12:16 Z imeimi2000 Rectangles (IOI19_rect) C++17
59 / 100
 5000 ms 423252 KB 
#include "rect.h"
#include <vector>
#include <set>
 
using namespace std;
typedef long long llong;
 
const short inf = 1e4;
int n, m;
short L[2501][2501];
short R[2501][2501];
short U[2501][2501];
short D[2501][2501];
short Lm[2501][2501];
short Rm[2501][2501];
short Um[2501][2501];
short Dm[2501][2501];
 
struct idxtree {
    const static int sz = 1 << 12;
    short seg[sz << 1];
    void init(vector<short> v) {
        for (int i = 1; i <= v.size(); ++i) seg[i + sz] = v[i - 1];
        for (int i = sz; i--; ) seg[i] = min(seg[i << 1], seg[i << 1 | 1]);
    }
    short query(int x, int y) {
        x += sz;
        y += sz;
        short ret = inf;
        while (x <= y) {
            if ((x & 1) == 1) ret = min(ret, seg[x++]);
            if ((y & 1) == 0) ret = min(ret, seg[y--]);
            x >>= 1;
            y >>= 1;
        }
        return ret;
    }
} Li[2501], Ri[2501], Ui[2501], Di[2501];
 
llong count_rectangles(vector<vector<int>> a) {
    n = a.size();
    m = a[0].size();
    //step 1
    for (int i = 1; i <= n; ++i) {
        vector<short> st;
        st.push_back(0);
        for (int j = 1; j <= m; ++j) {
            while (st.size() > 1 && a[i - 1][st.back() - 1] <= a[i - 1][j - 1])
                st.pop_back();
            L[i][j] = st.back();
            st.push_back(j);
        }
    }
    for (int i = 1; i <= n; ++i) {
        vector<short> st;
        st.push_back(m + 1);
        for (int j = m; j > 0; --j) {
            while (st.size() > 1 && a[i - 1][st.back() - 1] <= a[i - 1][j - 1])
                st.pop_back();
            R[i][j] = st.back();
            st.push_back(j);
        }
    }
    for (int i = 1; i <= m; ++i) {
        vector<short> st;
        st.push_back(0);
        for (int j = 1; j <= n; ++j) {
            while (st.size() > 1 && a[st.back() - 1][i - 1] <= a[j - 1][i - 1])
                st.pop_back();
            U[j][i] = st.back();
            st.push_back(j);
        }
    }
    for (int i = 1; i <= m; ++i) {
        vector<short> st;
        st.push_back(n + 1);
        for (int j = n; j > 0; --j) {
            while (st.size() > 1 && a[st.back() - 1][i - 1] <= a[j - 1][i - 1])
                st.pop_back();
            D[j][i] = st.back();
            st.push_back(j);
        }
    }
    //step 2
    for (int i = 1; i <= n; ++i) {
        vector<short> st;
        st.push_back(0);
        for (int j = 1; j <= m; ++j) {
            while (st.size() > 1 && a[i - 1][st.back() - 1] < a[i - 1][j - 1])
                st.pop_back();
            Lm[i][j] = st.back();
            st.push_back(j);
        }
    }
    for (int i = 1; i <= n; ++i) {
        vector<short> st;
        st.push_back(m + 1);
        for (int j = m; j > 0; --j) {
            while (st.size() > 1 && a[i - 1][st.back() - 1] < a[i - 1][j - 1])
                st.pop_back();
            Rm[i][j] = st.back();
            st.push_back(j);
        }
    }
    for (int i = 1; i <= m; ++i) {
        vector<short> st;
        st.push_back(0);
        for (int j = 1; j <= n; ++j) {
            while (st.size() > 1 && a[st.back() - 1][i - 1] < a[j - 1][i - 1])
                st.pop_back();
            Um[j][i] = st.back();
            st.push_back(j);
        }
    }
    for (int i = 1; i <= m; ++i) {
        vector<short> st;
        st.push_back(n + 1);
        for (int j = n; j > 0; --j) {
            while (st.size() > 1 && a[st.back() - 1][i - 1] < a[j - 1][i - 1])
                st.pop_back();
            Dm[j][i] = st.back();
            st.push_back(j);
        }
    }
    //step 3
    for (int i = 1; i <= m; ++i) {
        vector<short> Ls, Rs;
        for (int j = 1; j <= n; ++j) {
            Ls.push_back(-Lm[j][i]);
            Rs.push_back(Rm[j][i]);
        }
        Li[i].init(Ls);
        Ri[i].init(Rs);
    }
    for (int i = 1; i <= n; ++i) {
        vector<short> Us, Ds;
        for (int j = 1; j <= m; ++j) {
            Us.push_back(-Um[i][j]);
            Ds.push_back(Dm[i][j]);
        }
        Ui[i].init(Us);
        Di[i].init(Ds);
    }
    int ans = 0;
    set<llong> sp;
    for (int i = 2; i < n; ++i) {
        for (int j = 2; j < m; ++j) {
            int Lx = L[i][j] + 1;
            if (Lx == 1) continue;
            int Rx = R[i][j] - 1;
            if (Rx == m) continue;
            int Ux = U[i][j] + 1;
            if (Ux == 1) continue;
            int Dx = D[i][j] - 1;
            if (Dx == n) continue;
            llong idx = ((llong)(Lx << 12 | Rx)) << 24 | (Ux << 12 | Dx);
            if (sp.count(idx)) continue;
            sp.insert(idx);
            if (Ri[Lx - 1].query(Ux, Dx) - 1 < Rx) continue;
            if (-Li[Rx + 1].query(Ux, Dx) + 1 > Lx) continue;
            if (Di[Ux - 1].query(Lx, Rx) - 1 < Dx) continue;
            if (-Ui[Dx + 1].query(Lx, Rx) + 1 > Ux) continue;
            ++ans; 
        }
    }
    return ans;
}

Compilation message

rect.cpp: In member function 'void idxtree::init(std::vector<short int>)':
rect.cpp:23:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 1; i <= v.size(); ++i) seg[i + sz] = v[i - 1];
                         ~~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 5 ms 2812 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 1784 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 5 ms 2936 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 888 KB Output is correct
15 Correct 3 ms 1144 KB Output is correct
16 Correct 2 ms 632 KB Output is correct
17 Correct 2 ms 504 KB Output is correct
18 Correct 2 ms 504 KB Output is correct
19 Correct 5 ms 2812 KB Output is correct
20 Correct 1 ms 2424 KB Output is correct
21 Correct 2 ms 1016 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 5 ms 2812 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 1784 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 5 ms 2936 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 888 KB Output is correct
15 Correct 3 ms 1144 KB Output is correct
16 Correct 2 ms 632 KB Output is correct
17 Correct 13 ms 7160 KB Output is correct
18 Correct 13 ms 7160 KB Output is correct
19 Correct 13 ms 7160 KB Output is correct
20 Correct 12 ms 7036 KB Output is correct
21 Correct 13 ms 7036 KB Output is correct
22 Correct 13 ms 7160 KB Output is correct
23 Correct 13 ms 7160 KB Output is correct
24 Correct 10 ms 6008 KB Output is correct
25 Correct 2 ms 504 KB Output is correct
26 Correct 2 ms 504 KB Output is correct
27 Correct 5 ms 2812 KB Output is correct
28 Correct 1 ms 2424 KB Output is correct
29 Correct 2 ms 1016 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 5 ms 2812 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 1784 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 5 ms 2936 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 888 KB Output is correct
15 Correct 3 ms 1144 KB Output is correct
16 Correct 2 ms 632 KB Output is correct
17 Correct 13 ms 7160 KB Output is correct
18 Correct 13 ms 7160 KB Output is correct
19 Correct 13 ms 7160 KB Output is correct
20 Correct 12 ms 7036 KB Output is correct
21 Correct 13 ms 7036 KB Output is correct
22 Correct 13 ms 7160 KB Output is correct
23 Correct 13 ms 7160 KB Output is correct
24 Correct 10 ms 6008 KB Output is correct
25 Correct 47 ms 19184 KB Output is correct
26 Correct 46 ms 19192 KB Output is correct
27 Correct 46 ms 19128 KB Output is correct
28 Correct 42 ms 18296 KB Output is correct
29 Correct 51 ms 19064 KB Output is correct
30 Correct 51 ms 19064 KB Output is correct
31 Correct 49 ms 18680 KB Output is correct
32 Correct 49 ms 18808 KB Output is correct
33 Correct 2 ms 504 KB Output is correct
34 Correct 2 ms 504 KB Output is correct
35 Correct 5 ms 2812 KB Output is correct
36 Correct 1 ms 2424 KB Output is correct
37 Correct 2 ms 1016 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 5 ms 2812 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 1784 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 5 ms 2936 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 888 KB Output is correct
15 Correct 3 ms 1144 KB Output is correct
16 Correct 2 ms 632 KB Output is correct
17 Correct 13 ms 7160 KB Output is correct
18 Correct 13 ms 7160 KB Output is correct
19 Correct 13 ms 7160 KB Output is correct
20 Correct 12 ms 7036 KB Output is correct
21 Correct 13 ms 7036 KB Output is correct
22 Correct 13 ms 7160 KB Output is correct
23 Correct 13 ms 7160 KB Output is correct
24 Correct 10 ms 6008 KB Output is correct
25 Correct 47 ms 19184 KB Output is correct
26 Correct 46 ms 19192 KB Output is correct
27 Correct 46 ms 19128 KB Output is correct
28 Correct 42 ms 18296 KB Output is correct
29 Correct 51 ms 19064 KB Output is correct
30 Correct 51 ms 19064 KB Output is correct
31 Correct 49 ms 18680 KB Output is correct
32 Correct 49 ms 18808 KB Output is correct
33 Correct 173 ms 76536 KB Output is correct
34 Correct 177 ms 76572 KB Output is correct
35 Correct 171 ms 76664 KB Output is correct
36 Correct 172 ms 76636 KB Output is correct
37 Correct 511 ms 99468 KB Output is correct
38 Correct 497 ms 99540 KB Output is correct
39 Correct 511 ms 99416 KB Output is correct
40 Correct 480 ms 94500 KB Output is correct
41 Correct 336 ms 85980 KB Output is correct
42 Correct 424 ms 89624 KB Output is correct
43 Correct 745 ms 98740 KB Output is correct
44 Correct 712 ms 98788 KB Output is correct
45 Correct 328 ms 67576 KB Output is correct
46 Correct 317 ms 54996 KB Output is correct
47 Correct 605 ms 94816 KB Output is correct
48 Correct 614 ms 95248 KB Output is correct
49 Correct 2 ms 504 KB Output is correct
50 Correct 2 ms 504 KB Output is correct
51 Correct 5 ms 2812 KB Output is correct
52 Correct 1 ms 2424 KB Output is correct
53 Correct 2 ms 1016 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 61028 KB Output is correct
2 Correct 81 ms 51792 KB Output is correct
3 Correct 92 ms 60768 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 94 ms 60928 KB Output is correct
6 Correct 94 ms 60792 KB Output is correct
7 Correct 94 ms 60852 KB Output is correct
8 Correct 92 ms 60880 KB Output is correct
9 Correct 94 ms 60920 KB Output is correct
10 Correct 92 ms 60664 KB Output is correct
11 Correct 93 ms 60772 KB Output is correct

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 2326 ms 240152 KB Output is correct
3 Execution timed out 5067 ms 423252 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 5 ms 2812 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 1784 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct
11 Correct 5 ms 2808 KB Output is correct
12 Correct 5 ms 2936 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 888 KB Output is correct
15 Correct 3 ms 1144 KB Output is correct
16 Correct 2 ms 632 KB Output is correct
17 Correct 13 ms 7160 KB Output is correct
18 Correct 13 ms 7160 KB Output is correct
19 Correct 13 ms 7160 KB Output is correct
20 Correct 12 ms 7036 KB Output is correct
21 Correct 13 ms 7036 KB Output is correct
22 Correct 13 ms 7160 KB Output is correct
23 Correct 13 ms 7160 KB Output is correct
24 Correct 10 ms 6008 KB Output is correct
25 Correct 47 ms 19184 KB Output is correct
26 Correct 46 ms 19192 KB Output is correct
27 Correct 46 ms 19128 KB Output is correct
28 Correct 42 ms 18296 KB Output is correct
29 Correct 51 ms 19064 KB Output is correct
30 Correct 51 ms 19064 KB Output is correct
31 Correct 49 ms 18680 KB Output is correct
32 Correct 49 ms 18808 KB Output is correct
33 Correct 173 ms 76536 KB Output is correct
34 Correct 177 ms 76572 KB Output is correct
35 Correct 171 ms 76664 KB Output is correct
36 Correct 172 ms 76636 KB Output is correct
37 Correct 511 ms 99468 KB Output is correct
38 Correct 497 ms 99540 KB Output is correct
39 Correct 511 ms 99416 KB Output is correct
40 Correct 480 ms 94500 KB Output is correct
41 Correct 336 ms 85980 KB Output is correct
42 Correct 424 ms 89624 KB Output is correct
43 Correct 745 ms 98740 KB Output is correct
44 Correct 712 ms 98788 KB Output is correct
45 Correct 328 ms 67576 KB Output is correct
46 Correct 317 ms 54996 KB Output is correct
47 Correct 605 ms 94816 KB Output is correct
48 Correct 614 ms 95248 KB Output is correct
49 Correct 96 ms 61028 KB Output is correct
50 Correct 81 ms 51792 KB Output is correct
51 Correct 92 ms 60768 KB Output is correct
52 Correct 2 ms 504 KB Output is correct
53 Correct 94 ms 60928 KB Output is correct
54 Correct 94 ms 60792 KB Output is correct
55 Correct 94 ms 60852 KB Output is correct
56 Correct 92 ms 60880 KB Output is correct
57 Correct 94 ms 60920 KB Output is correct
58 Correct 92 ms 60664 KB Output is correct
59 Correct 93 ms 60772 KB Output is correct
60 Correct 3 ms 1144 KB Output is correct
61 Correct 2326 ms 240152 KB Output is correct
62 Execution timed out 5067 ms 423252 KB Time limit exceeded
63 Halted 0 ms 0 KB -