oj.uz

Submission #725165

# Submission time Handle Problem Language Result Execution time Memory
725165 2023-04-17T02:25:22 Z dooompy Rectangles (IOI19_rect) C++17
100 / 100
 2848 ms 595556 KB 
#include "bits/stdc++.h"
#include "rect.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}

template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("{" + string(#args) + "}", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

int lft[2505][2505];
int rht[2505][2505];
vector<pair<int, int>> interval[2505];
vector<pair<int, int>> otherrow[2505][2505];

struct segment {
    int l, r, last;

    bool operator<(segment o) const {
        return l < o.l;
    }
};

vector<segment> row[2505];

int bit[2505][2505];

void update(int id, int pos, int val) {
    for (; pos < 2505; pos += pos & -pos) {
        bit[id][pos] += val;
    }
}

int query(int id, int pos) {
    int sum = 0;
    for (; pos; pos -= pos & -pos) {
        sum += bit[id][pos];
    }

    return sum;
}

ll count_rectangles(vector<vector<int>> a) {
    int n = a.size();
    int m= a[0].size();

    if (min(n, m) <= 2) {
        return 0;
    }

    deque<int> dq;

    memset(lft, -1, sizeof(lft));
    memset(rht, -1, sizeof(rht));

    for (int i = 1; i <= n - 2; i++) {
        while (!dq.empty()) dq.pop_back();

        for (int j = 0; j < m; j++) {
            while (!dq.empty() && a[i][j] > a[i][dq.back()]) dq.pop_back();
            if (!dq.empty() && dq.back() != j-1) {
                lft[i][j] = dq.back();
                interval[i].push_back({dq.back(), j});
            }
            dq.push_back(j);
        }

        while (!dq.empty()) dq.pop_back();
        for (int j = m - 1; j >= 0; j--) {
            while (!dq.empty() && a[i][j] > a[i][dq.back()]) dq.pop_back();
            if (!dq.empty() && dq.back() != j+1) {
                rht[i][j] = dq.back();
                interval[i].push_back({j, dq.back()});
            }
            dq.push_back(j);
        }
    }

    for (int i = 1; i <= n-2; i++) {
        for (auto [l, r] : interval[i]) {
            if (lft[i][r] != l && rht[i][l] != r) continue;
            if (lft[i][r] == l) lft[i][r] = -1;
            if (rht[i][l] == r) rht[i][l] = -1;
            int nxt = i + 1;
            while (nxt <= n - 2 && (lft[nxt][r] == l || rht[nxt][l] == r)) {
                if (lft[nxt][r] == l) lft[nxt][r] = -1;
                if (rht[nxt][l] == r) rht[nxt][l] = -1;
                nxt++;
            }

            for (int j = i; j < nxt; j++) {
                row[j].push_back({l + 1, r - 1, nxt - 1});
            }
        }

        sort(row[i].begin(), row[i].end());
    }

    memset(lft,-1,sizeof(lft));
    memset(rht,-1,sizeof(rht));

    for (int i = 1; i <= m - 2; i++) {
        while (!dq.empty()) dq.pop_back();

        for (int j = 0; j < n; j++) {
            while (!dq.empty() && a[j][i] > a[dq.back()][i]) dq.pop_back();
            if (!dq.empty() && dq.back() != j-1) {
                lft[i][j] = dq.back();
                interval[i].push_back({dq.back(), j});
            }
            dq.push_back(j);
        }

        while (!dq.empty()) dq.pop_back();
        for (int j = n - 1; j >= 0; j--) {
            while (!dq.empty() && a[j][i] > a[dq.back()][i]) dq.pop_back();
            if (!dq.empty() && dq.back() != j+1) {
                rht[i][j] = dq.back();
                interval[i].push_back({j, dq.back()});
            }
            dq.push_back(j);
        }
    }

    for (int i = 1; i <= m - 2; i++) {
        for (auto [l, r] : interval[i]) {
            if (lft[i][r] != l && rht[i][l] != r) continue;
            if (lft[i][r] == l) lft[i][r] = -1;
            if (rht[i][l] == r) rht[i][l] = -1;
            int nxt = i + 1;
            while (nxt <= m - 2 && (lft[nxt][r] == l || rht[nxt][l] == r)) {
                if (lft[nxt][r] == l) lft[nxt][r] = -1;
                if (rht[nxt][l] == r) rht[nxt][l] = -1;
                nxt++;
            }

            for (int j = i; j < nxt; j++) {
                otherrow[l + 1][i].emplace_back(j, r - 1);
            }
        }
    }

    ll ans = 0;

    for (int i = 1; i <= n - 2; i++) {
        int cur = 1;
        vector<pair<int, int>> ops;
        for (auto [l, r, last] : row[i]) {
            while (cur <= l) {
                for (auto [col, lastrow] : otherrow[i][cur]) {
                    update(col, lastrow, 1);
                    ops.push_back({col, lastrow});
                }
                cur++;
            }

            ans += query(r, last);
        }

        while (!ops.empty()) {
            auto [col, lastrow] = ops.back();
            ops.pop_back();
            update(col, lastrow, -1);
        }
    }

    return ans;
}

//int main() {
//    ios_base::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
////    freopen("", "r", stdin);
////    freopen("", "w", stdout);
//    cout << count_rectangles({{4, 8, 7, 5, 6},
//    {7, 4, 10, 3, 5},
//    {9, 7, 20, 14, 2},
//    {9, 14, 7, 3, 6},
//    {5, 7, 5, 2, 7},
//    {4, 5, 13, 5, 6}});
//}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 196912 KB Output is correct
2 Correct 95 ms 197196 KB Output is correct
3 Correct 95 ms 197196 KB Output is correct
4 Correct 92 ms 197196 KB Output is correct
5 Correct 106 ms 196820 KB Output is correct
6 Correct 111 ms 197196 KB Output is correct
7 Correct 93 ms 196908 KB Output is correct
8 Correct 96 ms 197076 KB Output is correct
9 Correct 106 ms 197180 KB Output is correct
10 Correct 110 ms 197152 KB Output is correct
11 Correct 101 ms 197224 KB Output is correct
12 Correct 92 ms 197100 KB Output is correct
13 Correct 87 ms 147660 KB Output is correct
14 Correct 72 ms 147748 KB Output is correct
15 Correct 104 ms 196840 KB Output is correct
16 Correct 95 ms 196812 KB Output is correct
17 Correct 72 ms 147760 KB Output is correct
18 Correct 70 ms 147764 KB Output is correct
19 Correct 94 ms 197068 KB Output is correct
20 Correct 97 ms 196876 KB Output is correct
21 Correct 68 ms 147724 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 196912 KB Output is correct
2 Correct 95 ms 197196 KB Output is correct
3 Correct 95 ms 197196 KB Output is correct
4 Correct 92 ms 197196 KB Output is correct
5 Correct 106 ms 196820 KB Output is correct
6 Correct 111 ms 197196 KB Output is correct
7 Correct 93 ms 196908 KB Output is correct
8 Correct 96 ms 197076 KB Output is correct
9 Correct 106 ms 197180 KB Output is correct
10 Correct 110 ms 197152 KB Output is correct
11 Correct 101 ms 197224 KB Output is correct
12 Correct 92 ms 197100 KB Output is correct
13 Correct 87 ms 147660 KB Output is correct
14 Correct 72 ms 147748 KB Output is correct
15 Correct 104 ms 196840 KB Output is correct
16 Correct 95 ms 196812 KB Output is correct
17 Correct 72 ms 147760 KB Output is correct
18 Correct 70 ms 147764 KB Output is correct
19 Correct 94 ms 197068 KB Output is correct
20 Correct 97 ms 196876 KB Output is correct
21 Correct 68 ms 147724 KB Output is correct
22 Correct 103 ms 198040 KB Output is correct
23 Correct 97 ms 198044 KB Output is correct
24 Correct 96 ms 198040 KB Output is correct
25 Correct 99 ms 197852 KB Output is correct
26 Correct 97 ms 198048 KB Output is correct
27 Correct 96 ms 198064 KB Output is correct
28 Correct 99 ms 198092 KB Output is correct
29 Correct 98 ms 197364 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 196912 KB Output is correct
2 Correct 95 ms 197196 KB Output is correct
3 Correct 95 ms 197196 KB Output is correct
4 Correct 92 ms 197196 KB Output is correct
5 Correct 106 ms 196820 KB Output is correct
6 Correct 111 ms 197196 KB Output is correct
7 Correct 93 ms 196908 KB Output is correct
8 Correct 96 ms 197076 KB Output is correct
9 Correct 106 ms 197180 KB Output is correct
10 Correct 110 ms 197152 KB Output is correct
11 Correct 101 ms 197224 KB Output is correct
12 Correct 92 ms 197100 KB Output is correct
13 Correct 87 ms 147660 KB Output is correct
14 Correct 72 ms 147748 KB Output is correct
15 Correct 104 ms 196840 KB Output is correct
16 Correct 95 ms 196812 KB Output is correct
17 Correct 103 ms 198040 KB Output is correct
18 Correct 97 ms 198044 KB Output is correct
19 Correct 96 ms 198040 KB Output is correct
20 Correct 99 ms 197852 KB Output is correct
21 Correct 97 ms 198048 KB Output is correct
22 Correct 96 ms 198064 KB Output is correct
23 Correct 99 ms 198092 KB Output is correct
24 Correct 98 ms 197364 KB Output is correct
25 Correct 72 ms 147760 KB Output is correct
26 Correct 70 ms 147764 KB Output is correct
27 Correct 94 ms 197068 KB Output is correct
28 Correct 97 ms 196876 KB Output is correct
29 Correct 68 ms 147724 KB Output is correct
30 Correct 102 ms 201168 KB Output is correct
31 Correct 103 ms 201016 KB Output is correct
32 Correct 109 ms 201172 KB Output is correct
33 Correct 102 ms 200468 KB Output is correct
34 Correct 109 ms 201420 KB Output is correct
35 Correct 111 ms 201308 KB Output is correct
36 Correct 112 ms 201276 KB Output is correct
37 Correct 105 ms 201264 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 196912 KB Output is correct
2 Correct 95 ms 197196 KB Output is correct
3 Correct 95 ms 197196 KB Output is correct
4 Correct 92 ms 197196 KB Output is correct
5 Correct 106 ms 196820 KB Output is correct
6 Correct 111 ms 197196 KB Output is correct
7 Correct 93 ms 196908 KB Output is correct
8 Correct 96 ms 197076 KB Output is correct
9 Correct 106 ms 197180 KB Output is correct
10 Correct 110 ms 197152 KB Output is correct
11 Correct 101 ms 197224 KB Output is correct
12 Correct 92 ms 197100 KB Output is correct
13 Correct 87 ms 147660 KB Output is correct
14 Correct 72 ms 147748 KB Output is correct
15 Correct 104 ms 196840 KB Output is correct
16 Correct 95 ms 196812 KB Output is correct
17 Correct 103 ms 198040 KB Output is correct
18 Correct 97 ms 198044 KB Output is correct
19 Correct 96 ms 198040 KB Output is correct
20 Correct 99 ms 197852 KB Output is correct
21 Correct 97 ms 198048 KB Output is correct
22 Correct 96 ms 198064 KB Output is correct
23 Correct 99 ms 198092 KB Output is correct
24 Correct 98 ms 197364 KB Output is correct
25 Correct 102 ms 201168 KB Output is correct
26 Correct 103 ms 201016 KB Output is correct
27 Correct 109 ms 201172 KB Output is correct
28 Correct 102 ms 200468 KB Output is correct
29 Correct 109 ms 201420 KB Output is correct
30 Correct 111 ms 201308 KB Output is correct
31 Correct 112 ms 201276 KB Output is correct
32 Correct 105 ms 201264 KB Output is correct
33 Correct 72 ms 147760 KB Output is correct
34 Correct 70 ms 147764 KB Output is correct
35 Correct 94 ms 197068 KB Output is correct
36 Correct 97 ms 196876 KB Output is correct
37 Correct 68 ms 147724 KB Output is correct
38 Correct 191 ms 225488 KB Output is correct
39 Correct 250 ms 225612 KB Output is correct
40 Correct 188 ms 220952 KB Output is correct
41 Correct 195 ms 220856 KB Output is correct
42 Correct 180 ms 232612 KB Output is correct
43 Correct 186 ms 232624 KB Output is correct
44 Correct 186 ms 232620 KB Output is correct
45 Correct 184 ms 231208 KB Output is correct
46 Correct 188 ms 219336 KB Output is correct
47 Correct 186 ms 222292 KB Output is correct
48 Correct 268 ms 235324 KB Output is correct
49 Correct 298 ms 235596 KB Output is correct
50 Correct 181 ms 216076 KB Output is correct
51 Correct 194 ms 219612 KB Output is correct
52 Correct 263 ms 233960 KB Output is correct
53 Correct 269 ms 233688 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 221632 KB Output is correct
2 Correct 105 ms 217952 KB Output is correct
3 Correct 102 ms 196932 KB Output is correct
4 Correct 72 ms 147728 KB Output is correct
5 Correct 102 ms 206644 KB Output is correct
6 Correct 101 ms 206440 KB Output is correct
7 Correct 102 ms 206164 KB Output is correct
8 Correct 100 ms 205456 KB Output is correct
9 Correct 98 ms 205052 KB Output is correct
10 Correct 76 ms 147724 KB Output is correct
11 Correct 73 ms 147748 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 147760 KB Output is correct
2 Correct 70 ms 147764 KB Output is correct
3 Correct 94 ms 197068 KB Output is correct
4 Correct 97 ms 196876 KB Output is correct
5 Correct 68 ms 147724 KB Output is correct
6 Correct 95 ms 196940 KB Output is correct
7 Correct 605 ms 305092 KB Output is correct
8 Correct 1208 ms 413352 KB Output is correct
9 Correct 1191 ms 413808 KB Output is correct
10 Correct 1293 ms 414072 KB Output is correct
11 Correct 200 ms 221852 KB Output is correct
12 Correct 351 ms 243752 KB Output is correct
13 Correct 373 ms 246740 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 196912 KB Output is correct
2 Correct 95 ms 197196 KB Output is correct
3 Correct 95 ms 197196 KB Output is correct
4 Correct 92 ms 197196 KB Output is correct
5 Correct 106 ms 196820 KB Output is correct
6 Correct 111 ms 197196 KB Output is correct
7 Correct 93 ms 196908 KB Output is correct
8 Correct 96 ms 197076 KB Output is correct
9 Correct 106 ms 197180 KB Output is correct
10 Correct 110 ms 197152 KB Output is correct
11 Correct 101 ms 197224 KB Output is correct
12 Correct 92 ms 197100 KB Output is correct
13 Correct 87 ms 147660 KB Output is correct
14 Correct 72 ms 147748 KB Output is correct
15 Correct 104 ms 196840 KB Output is correct
16 Correct 95 ms 196812 KB Output is correct
17 Correct 103 ms 198040 KB Output is correct
18 Correct 97 ms 198044 KB Output is correct
19 Correct 96 ms 198040 KB Output is correct
20 Correct 99 ms 197852 KB Output is correct
21 Correct 97 ms 198048 KB Output is correct
22 Correct 96 ms 198064 KB Output is correct
23 Correct 99 ms 198092 KB Output is correct
24 Correct 98 ms 197364 KB Output is correct
25 Correct 102 ms 201168 KB Output is correct
26 Correct 103 ms 201016 KB Output is correct
27 Correct 109 ms 201172 KB Output is correct
28 Correct 102 ms 200468 KB Output is correct
29 Correct 109 ms 201420 KB Output is correct
30 Correct 111 ms 201308 KB Output is correct
31 Correct 112 ms 201276 KB Output is correct
32 Correct 105 ms 201264 KB Output is correct
33 Correct 191 ms 225488 KB Output is correct
34 Correct 250 ms 225612 KB Output is correct
35 Correct 188 ms 220952 KB Output is correct
36 Correct 195 ms 220856 KB Output is correct
37 Correct 180 ms 232612 KB Output is correct
38 Correct 186 ms 232624 KB Output is correct
39 Correct 186 ms 232620 KB Output is correct
40 Correct 184 ms 231208 KB Output is correct
41 Correct 188 ms 219336 KB Output is correct
42 Correct 186 ms 222292 KB Output is correct
43 Correct 268 ms 235324 KB Output is correct
44 Correct 298 ms 235596 KB Output is correct
45 Correct 181 ms 216076 KB Output is correct
46 Correct 194 ms 219612 KB Output is correct
47 Correct 263 ms 233960 KB Output is correct
48 Correct 269 ms 233688 KB Output is correct
49 Correct 103 ms 221632 KB Output is correct
50 Correct 105 ms 217952 KB Output is correct
51 Correct 102 ms 196932 KB Output is correct
52 Correct 72 ms 147728 KB Output is correct
53 Correct 102 ms 206644 KB Output is correct
54 Correct 101 ms 206440 KB Output is correct
55 Correct 102 ms 206164 KB Output is correct
56 Correct 100 ms 205456 KB Output is correct
57 Correct 98 ms 205052 KB Output is correct
58 Correct 76 ms 147724 KB Output is correct
59 Correct 73 ms 147748 KB Output is correct
60 Correct 95 ms 196940 KB Output is correct
61 Correct 605 ms 305092 KB Output is correct
62 Correct 1208 ms 413352 KB Output is correct
63 Correct 1191 ms 413808 KB Output is correct
64 Correct 1293 ms 414072 KB Output is correct
65 Correct 200 ms 221852 KB Output is correct
66 Correct 351 ms 243752 KB Output is correct
67 Correct 373 ms 246740 KB Output is correct
68 Correct 72 ms 147760 KB Output is correct
69 Correct 70 ms 147764 KB Output is correct
70 Correct 94 ms 197068 KB Output is correct
71 Correct 97 ms 196876 KB Output is correct
72 Correct 68 ms 147724 KB Output is correct
73 Correct 1183 ms 469992 KB Output is correct
74 Correct 1589 ms 470484 KB Output is correct
75 Correct 885 ms 405808 KB Output is correct
76 Correct 835 ms 405380 KB Output is correct
77 Correct 1343 ms 551292 KB Output is correct
78 Correct 1666 ms 427720 KB Output is correct
79 Correct 1715 ms 432692 KB Output is correct
80 Correct 2848 ms 592992 KB Output is correct
81 Correct 1672 ms 428924 KB Output is correct
82 Correct 2178 ms 501048 KB Output is correct
83 Correct 2789 ms 595556 KB Output is correct
84 Correct 1510 ms 417792 KB Output is correct
85 Correct 2551 ms 574704 KB Output is correct
86 Correct 2451 ms 565216 KB Output is correct
87 Correct 766 ms 393156 KB Output is correct
88 Correct 1307 ms 551868 KB Output is correct
89 Correct 1301 ms 551592 KB Output is correct
90 Correct 1255 ms 551300 KB Output is correct