oj.uz

답안 #1071245

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1071245 2024-08-23T06:12:21 Z j_vdd16 Rectangles (IOI19_rect) C++17
72 / 100
 5000 ms 1048576 KB 
#include "rect.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define ll long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

struct MSTree {
    int n, N;
    vvi tree;

    MSTree() = default;
    MSTree(const vvi& values, int sz) {
        n = sz;
        N = 1;
        while (N < n) N *= 2;

        tree = vvi(2 * N);
        loop(i, values.size()) {
            for (int j : values[i]) {
                tree[N + j].push_back(i); 
            }
        }

        for (int i = N - 1; i >= 1; i--) {
            tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
        }
    }

    vi merge(const vi& a, const vi& b) {
        int idx1 = 0, idx2 = 0;
        vi out;
        while (idx1 < a.size() && idx2 < b.size()) {
            if (a[idx1] < b[idx2]) {
                idx1++;
            }
            else if (a[idx1] > b[idx2]) {
                idx2++;
            }
            else {
                out.push_back(a[idx1]);
                idx1++;
                idx2++;
            }
        }

        return out;
    }

    vi getRange(int l, int r, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1) {
            tr = N;
        }

        if (tr <= l || tl >= r) {
            cout << "ERROR" << endl;
            return {};
        }

        if (tl >= l && tr <= r) {
            return tree[i];
        }

        int tm = (tl + tr) / 2;
        if (tm >= r) {
            return getRange(l, r, i * 2, tl, tm);
        }
        if (tm <= l) {
            return getRange(l, r, i * 2 + 1, tm, tr);
        }
        return merge(getRange(l, r, i * 2, tl, tm), getRange(l, r, i * 2 + 1, tm, tr));
    }
};

long long count_rectangles(vvi a) {
	int n = a.size();
    int m = a[0].size();

    vector<vvi> validRows(m, vvi(m));
    for (int i = 1; i < n - 1; i++) {
        map<int, vi, greater<int>> values;
        loop(j, m) {
            values[a[i][j]].push_back(j);
        }

        map<int, int> rec;
        for (auto [val, vec] : values) {
            loop(idx, vec.size()) {
                if (rec.size() == 0) {
                    rec[vec[idx]] = val;
                    continue;
                }

                auto next = rec.upper_bound(vec[idx]);
                if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
                    validRows[vec[idx]][next->first].push_back(i);
                }

                if (next != rec.begin()) {
                    next--;
                    if (vec[idx] - next->first > 1) {
                        validRows[next->first][vec[idx]].push_back(i);
                    }
                }

                rec[vec[idx]] = val;
            }
        }
    }
    vector<vvi> validCols(n, vvi(n));
    for (int j = 1; j < m - 1; j++) {
        map<int, vi, greater<int>> values;
        loop(i, n) {
            values[a[i][j]].push_back(i);
        }
        
        map<int, int> rec;
        for (auto [val, vec] : values) {
            loop(idx, vec.size()) {
                if (rec.size() == 0) {
                    rec[vec[idx]] = val;
                    continue;
                }

                auto next = rec.upper_bound(vec[idx]);
                if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
                    validCols[vec[idx]][next->first].push_back(j);
                }

                if (next != rec.begin()) {
                    next--;
                    if (vec[idx] - next->first > 1) {
                        validCols[next->first][vec[idx]].push_back(j);
                    }
                }

                rec[vec[idx]] = val;
            }
        }
    }

    vector<MSTree> trees(n);
    loop(i, n) {
        trees[i] = MSTree(validCols[i], m);
        validCols[i].clear();
    }

    //bottleneck
    ll result = 0;
    for (int j1 = 0; j1 < m; j1++) {
        for (int j2 = j1 + 2; j2 < m; j2++) {
            const auto& valid = validRows[j1][j2];

            int furthest = -1;
            loop(idx, valid.size()) {
                //this happens O(n * m) times

                if (furthest < idx) {
                    furthest = idx;
                    while (furthest < valid.size() - 1 && valid[furthest + 1] == valid[furthest] + 1) {
                        furthest++;
                    }
                }

                vi validIndices = trees[valid[idx] - 1].getRange(j1 + 1, j2 - 1 + 1);
                auto upp = --upper_bound(all(validIndices), valid[furthest] + 1);
                int extra = upp - validIndices.begin() + 1;

                result += extra;

                // for (int idx2 = idx; idx2 <= furthest; idx2++) {
                //     const auto& relevantCols = validCols[valid[idx] - 1][valid[idx2] + 1];
                //     auto start = lower_bound(all(relevantCols), j1 + 1);
                //     auto end = lower_bound(all(relevantCols), j2 - 1);

                //     if (start != relevantCols.end() && end != relevantCols.end() && *start == j1 + 1 && *end == j2 - 1 && (end - start) == j2 - j1 - 2) {   
                //         result++;
                //     }
                // }
            }
        }
    }

    return result;
}

Compilation message

rect.cpp: In constructor 'MSTree::MSTree(const vvi&, int)':
rect.cpp:20:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define loop(X, N) for(int X = 0; X < (N); X++)
      |                                     ^
rect.cpp:45:9: note: in expansion of macro 'loop'
   45 |         loop(i, values.size()) {
      |         ^~~~
rect.cpp: In member function 'vi MSTree::merge(const vi&, const vi&)':
rect.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         while (idx1 < a.size() && idx2 < b.size()) {
      |                ~~~~~^~~~~~~~~~
rect.cpp:59:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         while (idx1 < a.size() && idx2 < b.size()) {
      |                                   ~~~~~^~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(vvi)':
rect.cpp:20:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define loop(X, N) for(int X = 0; X < (N); X++)
      |                                     ^
rect.cpp:114:13: note: in expansion of macro 'loop'
  114 |             loop(idx, vec.size()) {
      |             ^~~~
rect.cpp:121:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |                 if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
      |                                           ~~~~^~~~~~~~~~~~~~~~~
rect.cpp:20:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define loop(X, N) for(int X = 0; X < (N); X++)
      |                                     ^
rect.cpp:145:13: note: in expansion of macro 'loop'
  145 |             loop(idx, vec.size()) {
      |             ^~~~
rect.cpp:152:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |                 if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
      |                                           ~~~~^~~~~~~~~~~~~~~~~
rect.cpp:20:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define loop(X, N) for(int X = 0; X < (N); X++)
      |                                     ^
rect.cpp:181:13: note: in expansion of macro 'loop'
  181 |             loop(idx, valid.size()) {
      |             ^~~~
rect.cpp:186:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |                     while (furthest < valid.size() - 1 && valid[furthest + 1] == valid[furthest] + 1) {
      |                            ~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 8 ms 1624 KB Output is correct
23 Correct 10 ms 1624 KB Output is correct
24 Correct 9 ms 1628 KB Output is correct
25 Correct 3 ms 1368 KB Output is correct
26 Correct 5 ms 1384 KB Output is correct
27 Correct 5 ms 1372 KB Output is correct
28 Correct 5 ms 1376 KB Output is correct
29 Correct 4 ms 764 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 8 ms 1624 KB Output is correct
18 Correct 10 ms 1624 KB Output is correct
19 Correct 9 ms 1628 KB Output is correct
20 Correct 3 ms 1368 KB Output is correct
21 Correct 5 ms 1384 KB Output is correct
22 Correct 5 ms 1372 KB Output is correct
23 Correct 5 ms 1376 KB Output is correct
24 Correct 4 ms 764 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 36 ms 7512 KB Output is correct
31 Correct 30 ms 7512 KB Output is correct
32 Correct 48 ms 7516 KB Output is correct
33 Correct 15 ms 5468 KB Output is correct
34 Correct 34 ms 6060 KB Output is correct
35 Correct 36 ms 5944 KB Output is correct
36 Correct 38 ms 5968 KB Output is correct
37 Correct 37 ms 5964 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 8 ms 1624 KB Output is correct
18 Correct 10 ms 1624 KB Output is correct
19 Correct 9 ms 1628 KB Output is correct
20 Correct 3 ms 1368 KB Output is correct
21 Correct 5 ms 1384 KB Output is correct
22 Correct 5 ms 1372 KB Output is correct
23 Correct 5 ms 1376 KB Output is correct
24 Correct 4 ms 764 KB Output is correct
25 Correct 36 ms 7512 KB Output is correct
26 Correct 30 ms 7512 KB Output is correct
27 Correct 48 ms 7516 KB Output is correct
28 Correct 15 ms 5468 KB Output is correct
29 Correct 34 ms 6060 KB Output is correct
30 Correct 36 ms 5944 KB Output is correct
31 Correct 38 ms 5968 KB Output is correct
32 Correct 37 ms 5964 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 354 ms 76476 KB Output is correct
39 Correct 313 ms 76404 KB Output is correct
40 Correct 322 ms 70512 KB Output is correct
41 Correct 290 ms 70724 KB Output is correct
42 Correct 606 ms 93960 KB Output is correct
43 Correct 589 ms 94032 KB Output is correct
44 Correct 585 ms 93984 KB Output is correct
45 Correct 546 ms 88108 KB Output is correct
46 Correct 266 ms 65700 KB Output is correct
47 Correct 239 ms 67648 KB Output is correct
48 Correct 487 ms 73292 KB Output is correct
49 Correct 578 ms 73248 KB Output is correct
50 Correct 251 ms 39720 KB Output is correct
51 Correct 245 ms 39760 KB Output is correct
52 Correct 482 ms 72784 KB Output is correct
53 Correct 551 ms 72952 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 148052 KB Output is correct
2 Correct 79 ms 107348 KB Output is correct
3 Correct 67 ms 147960 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 69 ms 148220 KB Output is correct
6 Correct 77 ms 148356 KB Output is correct
7 Correct 75 ms 148308 KB Output is correct
8 Correct 84 ms 148308 KB Output is correct
9 Correct 72 ms 148256 KB Output is correct
10 Correct 67 ms 147540 KB Output is correct
11 Correct 106 ms 147644 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1491 ms 455760 KB Output is correct
8 Correct 3414 ms 890916 KB Output is correct
9 Correct 3345 ms 901776 KB Output is correct
10 Correct 3225 ms 902128 KB Output is correct
11 Correct 793 ms 453024 KB Output is correct
12 Correct 1461 ms 819536 KB Output is correct
13 Correct 1547 ms 840528 KB Output is correct

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 8 ms 1624 KB Output is correct
18 Correct 10 ms 1624 KB Output is correct
19 Correct 9 ms 1628 KB Output is correct
20 Correct 3 ms 1368 KB Output is correct
21 Correct 5 ms 1384 KB Output is correct
22 Correct 5 ms 1372 KB Output is correct
23 Correct 5 ms 1376 KB Output is correct
24 Correct 4 ms 764 KB Output is correct
25 Correct 36 ms 7512 KB Output is correct
26 Correct 30 ms 7512 KB Output is correct
27 Correct 48 ms 7516 KB Output is correct
28 Correct 15 ms 5468 KB Output is correct
29 Correct 34 ms 6060 KB Output is correct
30 Correct 36 ms 5944 KB Output is correct
31 Correct 38 ms 5968 KB Output is correct
32 Correct 37 ms 5964 KB Output is correct
33 Correct 354 ms 76476 KB Output is correct
34 Correct 313 ms 76404 KB Output is correct
35 Correct 322 ms 70512 KB Output is correct
36 Correct 290 ms 70724 KB Output is correct
37 Correct 606 ms 93960 KB Output is correct
38 Correct 589 ms 94032 KB Output is correct
39 Correct 585 ms 93984 KB Output is correct
40 Correct 546 ms 88108 KB Output is correct
41 Correct 266 ms 65700 KB Output is correct
42 Correct 239 ms 67648 KB Output is correct
43 Correct 487 ms 73292 KB Output is correct
44 Correct 578 ms 73248 KB Output is correct
45 Correct 251 ms 39720 KB Output is correct
46 Correct 245 ms 39760 KB Output is correct
47 Correct 482 ms 72784 KB Output is correct
48 Correct 551 ms 72952 KB Output is correct
49 Correct 71 ms 148052 KB Output is correct
50 Correct 79 ms 107348 KB Output is correct
51 Correct 67 ms 147960 KB Output is correct
52 Correct 1 ms 348 KB Output is correct
53 Correct 69 ms 148220 KB Output is correct
54 Correct 77 ms 148356 KB Output is correct
55 Correct 75 ms 148308 KB Output is correct
56 Correct 84 ms 148308 KB Output is correct
57 Correct 72 ms 148256 KB Output is correct
58 Correct 67 ms 147540 KB Output is correct
59 Correct 106 ms 147644 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 1491 ms 455760 KB Output is correct
62 Correct 3414 ms 890916 KB Output is correct
63 Correct 3345 ms 901776 KB Output is correct
64 Correct 3225 ms 902128 KB Output is correct
65 Correct 793 ms 453024 KB Output is correct
66 Correct 1461 ms 819536 KB Output is correct
67 Correct 1547 ms 840528 KB Output is correct
68 Correct 0 ms 348 KB Output is correct
69 Correct 0 ms 348 KB Output is correct
70 Correct 1 ms 348 KB Output is correct
71 Correct 0 ms 348 KB Output is correct
72 Correct 0 ms 348 KB Output is correct
73 Execution timed out 5055 ms 1048576 KB Time limit exceeded
74 Halted 0 ms 0 KB -