oj.uz

Submission #373876

# Submission time Handle Problem Language Result Execution time Memory
373876 2021-03-06T01:44:36 Z ijxjdjd Rectangles (IOI19_rect) C++14
100 / 100
 4964 ms 953156 KB 
#include "rect.h"
#include <bits/stdc++.h>

#define f first
#define s second


const int MAXN = 2500;
using ll = long long;
struct interval {
    int l, r;
    int i;
};
std::vector<interval> right;
std::vector<interval> down;
std::vector<std::pair<int, int>> rightP[MAXN][MAXN];
std::vector<std::pair<int, int>> downP[MAXN][MAXN];
std::vector<std::vector<int>> a;
int N, M;
void setPairs() {
    std::vector<interval> cur;
    for (auto& d : right) {
        if (cur.size() == 0 || d.l != cur.back().l || d.r != cur.back().r || d.i != cur.back().i+1) {
            if (cur.size()) {
                int lst = cur.back().i;
                while (cur.size()) {
                    rightP[cur.back().i][cur.back().l].push_back({lst, cur.back().r});
                    cur.pop_back();
                }
            }
        }
        cur.push_back(d);
    }
    if (cur.size()) {
        int lst = cur.back().i;
        while (cur.size()) {
            rightP[cur.back().i][cur.back().l].push_back({lst, cur.back().r});
            cur.pop_back();
        }
    }
    for (auto& d : down) {
        if (cur.size() == 0 || d.l != cur.back().l || d.r != cur.back().r || d.i != cur.back().i+1) {
            if (cur.size()) {
                int lst = cur.back().i;
                while (cur.size()) {
                    downP[cur.back().l][cur.back().i].push_back({cur.back().r, lst});
                    cur.pop_back();
                }
            }
        }
        cur.push_back(d);
    }
    if (cur.size()) {
        int lst = cur.back().i;
        while (cur.size()) {
            downP[cur.back().l][cur.back().i].push_back({cur.back().r, lst});
            cur.pop_back();
        }
    }
}
void getIntervals() {
//    for (int i = 1; i < N-1; i++) {
//        for (int j = 1; j < M-1; j++) {
//            int mx = 0;
//            for (int k = j; k < M-1; k++) {
//                mx = std::max(mx, a[i][k]);
//                if (a[i][j-1] > mx && a[i][k+1] > mx) {
//                    right[i][j].insert(k);
//                }
//            }
//        }
//    }
//    for (int j = 1; j < M-1; j++) {
//        for (int i = 1; i < N-1; i++) {
//            int mx = 0;
//            for (int k = i; k < N-1; k++) {
//                mx = std::max(mx, a[k][j]);
//                if (a[i-1][j] > mx && a[k+1][j] > mx) {
//                    down[i][j].insert(k);
//                }
//            }
//        }
//    }
    for (int i = 1; i < N-1; i++) {
        std::stack<std::pair<int, int>> st;
        st.push({a[i][0], 0});
        for (int j = 1; j < M; j++) {
            bool eq = false;
            while (st.size() && a[i][j] >= st.top().f) {
                if (st.top().s + 1 <= j-1) {
//                    if (!right[i][st.top().s+1].count(j-1)) {
//                        std::cout << "I inside"<< '\n';
//                    }
                    right.push_back({st.top().s+1, j-1, i});
                }
                eq = (a[i][j] == st.top().f);
                st.pop();
            }
            if (!eq) {
                if (st.size() && st.top().s + 1 <= j-1) {
//                    if (!right[i][st.top().s+1].count(j-1)) {
//                        std::cout << "I out"<< '\n';
//
                    right.push_back({st.top().s+1, j-1, i});
                }
            }
            st.push({a[i][j], j});
        }
    }
    for (int j = 1; j < M-1; j++) {
        std::stack<std::pair<int, int>> st;
        st.push({a[0][j], 0});
        for (int i = 1; i < N; i++) {
            bool eq = false;
            while (st.size() && a[i][j] >= st.top().f) {
                if (st.top().s + 1 <= i-1) {
//                    if (!down[st.top().s+1][j].count(i-1)) {
//                        std::cout << st.top().s+1 << " " << j << " " << i-1 <<'\n';
//                    }
                    down.push_back({st.top().s+1, i-1, j});
                }
                eq = (a[i][j] == st.top().f);
                st.pop();
            }
            if (!eq) {
                if (st.size() && st.top().s + 1 <= i-1) {
//                    if (!down[st.top().s+1][j].count(i-1)) {
//                        std::cout << st.top().s+1 << " " << j << " " << i-1 <<'\n';
//                    }
                    down.push_back({st.top().s+1, i-1, j});
                }
            }
            st.push({a[i][j], i});
        }
    }
    auto comp = [] (const interval& lhs, const interval& rhs) {
        if (lhs.l != rhs.l) {
            return lhs.l < rhs.l;
        }
        else if (rhs.r != lhs.r) {
            return lhs.r < rhs.r;
        }
        else {
            return lhs.i < rhs.i;
        }
    };
    sort(down.begin(), down.end(), comp);
    sort(right.begin(), right.end(), comp);
    setPairs();
}
int fen[MAXN];
void add(int val, int id) {
    for (;id<MAXN;id=(id|(id+1))) {
        fen[id]+=val;
    }
}
int sm(int r) {
    int rs = 0;
    for (;r >= 0; r=(r&(r+1)) - 1) {
        rs += fen[r];
    }
    return rs;
}
int sm(int l, int r) {
    return sm(r) - sm(l-1);
}
long long count_rectangles(std::vector<std::vector<int> > board) {
    a = board;
    N = a.size();
    M = a[0].size();
    if (N <= 2 || M <= 2) {
        return 0;
    }
    getIntervals();
    ll res = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            std::sort(rightP[i][j].begin(), rightP[i][j].end());
            std::sort(downP[i][j].begin(), downP[i][j].end());
            int u = 0;
            for (auto& p : rightP[i][j]) {
                while (u < downP[i][j].size() && downP[i][j][u].f <= p.f) {
                    add(1, downP[i][j][u].s);
                    u++;
                }
                res += sm(p.s, MAXN-1);
//                for (auto& u : downP[i][j]) {
//                    if (u.f <= p.f && u.s >= p.s) {
//                        res++;
//                    }
//                }
            }
//            memset(fen, 0, sizeof(fen));
            while (--u>= 0) {
                add(-1, downP[i][j][u].s);
            }
        }
    }
    return res;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:182:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |                 while (u < downP[i][j].size() && downP[i][j][u].f <= p.f) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 293868 KB Output is correct
2 Correct 207 ms 293996 KB Output is correct
3 Correct 199 ms 293996 KB Output is correct
4 Correct 200 ms 293996 KB Output is correct
5 Correct 208 ms 293868 KB Output is correct
6 Correct 202 ms 293996 KB Output is correct
7 Correct 215 ms 293868 KB Output is correct
8 Correct 208 ms 293868 KB Output is correct
9 Correct 205 ms 293996 KB Output is correct
10 Correct 203 ms 293868 KB Output is correct
11 Correct 203 ms 293868 KB Output is correct
12 Correct 204 ms 293956 KB Output is correct
13 Correct 210 ms 293996 KB Output is correct
14 Correct 197 ms 293868 KB Output is correct
15 Correct 204 ms 293868 KB Output is correct
16 Correct 201 ms 293868 KB Output is correct
17 Correct 202 ms 293868 KB Output is correct
18 Correct 204 ms 293868 KB Output is correct
19 Correct 213 ms 293868 KB Output is correct
20 Correct 197 ms 293868 KB Output is correct
21 Correct 205 ms 293868 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 293868 KB Output is correct
2 Correct 207 ms 293996 KB Output is correct
3 Correct 199 ms 293996 KB Output is correct
4 Correct 200 ms 293996 KB Output is correct
5 Correct 208 ms 293868 KB Output is correct
6 Correct 202 ms 293996 KB Output is correct
7 Correct 215 ms 293868 KB Output is correct
8 Correct 208 ms 293868 KB Output is correct
9 Correct 205 ms 293996 KB Output is correct
10 Correct 203 ms 293868 KB Output is correct
11 Correct 203 ms 293868 KB Output is correct
12 Correct 204 ms 293956 KB Output is correct
13 Correct 210 ms 293996 KB Output is correct
14 Correct 197 ms 293868 KB Output is correct
15 Correct 204 ms 293868 KB Output is correct
16 Correct 201 ms 293868 KB Output is correct
17 Correct 202 ms 293868 KB Output is correct
18 Correct 204 ms 293868 KB Output is correct
19 Correct 213 ms 293868 KB Output is correct
20 Correct 197 ms 293868 KB Output is correct
21 Correct 205 ms 293868 KB Output is correct
22 Correct 205 ms 294636 KB Output is correct
23 Correct 203 ms 294508 KB Output is correct
24 Correct 225 ms 294508 KB Output is correct
25 Correct 210 ms 294124 KB Output is correct
26 Correct 202 ms 294380 KB Output is correct
27 Correct 204 ms 294252 KB Output is correct
28 Correct 202 ms 294252 KB Output is correct
29 Correct 202 ms 294124 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 293868 KB Output is correct
2 Correct 207 ms 293996 KB Output is correct
3 Correct 199 ms 293996 KB Output is correct
4 Correct 200 ms 293996 KB Output is correct
5 Correct 208 ms 293868 KB Output is correct
6 Correct 202 ms 293996 KB Output is correct
7 Correct 215 ms 293868 KB Output is correct
8 Correct 208 ms 293868 KB Output is correct
9 Correct 205 ms 293996 KB Output is correct
10 Correct 203 ms 293868 KB Output is correct
11 Correct 203 ms 293868 KB Output is correct
12 Correct 204 ms 293956 KB Output is correct
13 Correct 210 ms 293996 KB Output is correct
14 Correct 197 ms 293868 KB Output is correct
15 Correct 204 ms 293868 KB Output is correct
16 Correct 201 ms 293868 KB Output is correct
17 Correct 205 ms 294636 KB Output is correct
18 Correct 203 ms 294508 KB Output is correct
19 Correct 225 ms 294508 KB Output is correct
20 Correct 210 ms 294124 KB Output is correct
21 Correct 202 ms 294380 KB Output is correct
22 Correct 204 ms 294252 KB Output is correct
23 Correct 202 ms 294252 KB Output is correct
24 Correct 202 ms 294124 KB Output is correct
25 Correct 202 ms 293868 KB Output is correct
26 Correct 204 ms 293868 KB Output is correct
27 Correct 213 ms 293868 KB Output is correct
28 Correct 197 ms 293868 KB Output is correct
29 Correct 205 ms 293868 KB Output is correct
30 Correct 221 ms 297700 KB Output is correct
31 Correct 216 ms 297764 KB Output is correct
32 Correct 218 ms 297700 KB Output is correct
33 Correct 218 ms 295632 KB Output is correct
34 Correct 219 ms 296632 KB Output is correct
35 Correct 227 ms 296684 KB Output is correct
36 Correct 230 ms 296556 KB Output is correct
37 Correct 221 ms 296428 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 293868 KB Output is correct
2 Correct 207 ms 293996 KB Output is correct
3 Correct 199 ms 293996 KB Output is correct
4 Correct 200 ms 293996 KB Output is correct
5 Correct 208 ms 293868 KB Output is correct
6 Correct 202 ms 293996 KB Output is correct
7 Correct 215 ms 293868 KB Output is correct
8 Correct 208 ms 293868 KB Output is correct
9 Correct 205 ms 293996 KB Output is correct
10 Correct 203 ms 293868 KB Output is correct
11 Correct 203 ms 293868 KB Output is correct
12 Correct 204 ms 293956 KB Output is correct
13 Correct 210 ms 293996 KB Output is correct
14 Correct 197 ms 293868 KB Output is correct
15 Correct 204 ms 293868 KB Output is correct
16 Correct 201 ms 293868 KB Output is correct
17 Correct 205 ms 294636 KB Output is correct
18 Correct 203 ms 294508 KB Output is correct
19 Correct 225 ms 294508 KB Output is correct
20 Correct 210 ms 294124 KB Output is correct
21 Correct 202 ms 294380 KB Output is correct
22 Correct 204 ms 294252 KB Output is correct
23 Correct 202 ms 294252 KB Output is correct
24 Correct 202 ms 294124 KB Output is correct
25 Correct 221 ms 297700 KB Output is correct
26 Correct 216 ms 297764 KB Output is correct
27 Correct 218 ms 297700 KB Output is correct
28 Correct 218 ms 295632 KB Output is correct
29 Correct 219 ms 296632 KB Output is correct
30 Correct 227 ms 296684 KB Output is correct
31 Correct 230 ms 296556 KB Output is correct
32 Correct 221 ms 296428 KB Output is correct
33 Correct 202 ms 293868 KB Output is correct
34 Correct 204 ms 293868 KB Output is correct
35 Correct 213 ms 293868 KB Output is correct
36 Correct 197 ms 293868 KB Output is correct
37 Correct 205 ms 293868 KB Output is correct
38 Correct 337 ms 320820 KB Output is correct
39 Correct 311 ms 315988 KB Output is correct
40 Correct 338 ms 315988 KB Output is correct
41 Correct 284 ms 311128 KB Output is correct
42 Correct 489 ms 341700 KB Output is correct
43 Correct 452 ms 341700 KB Output is correct
44 Correct 459 ms 341700 KB Output is correct
45 Correct 447 ms 338500 KB Output is correct
46 Correct 321 ms 310240 KB Output is correct
47 Correct 342 ms 314332 KB Output is correct
48 Correct 513 ms 328936 KB Output is correct
49 Correct 538 ms 329036 KB Output is correct
50 Correct 357 ms 311520 KB Output is correct
51 Correct 371 ms 311264 KB Output is correct
52 Correct 500 ms 326604 KB Output is correct
53 Correct 491 ms 326732 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 294252 KB Output is correct
2 Correct 201 ms 294124 KB Output is correct
3 Correct 202 ms 293996 KB Output is correct
4 Correct 212 ms 293912 KB Output is correct
5 Correct 207 ms 294124 KB Output is correct
6 Correct 201 ms 294124 KB Output is correct
7 Correct 216 ms 294124 KB Output is correct
8 Correct 203 ms 293996 KB Output is correct
9 Correct 199 ms 293996 KB Output is correct
10 Correct 217 ms 293868 KB Output is correct
11 Correct 201 ms 293868 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 293868 KB Output is correct
2 Correct 204 ms 293868 KB Output is correct
3 Correct 213 ms 293868 KB Output is correct
4 Correct 197 ms 293868 KB Output is correct
5 Correct 205 ms 293868 KB Output is correct
6 Correct 203 ms 293924 KB Output is correct
7 Correct 935 ms 389544 KB Output is correct
8 Correct 1856 ms 513020 KB Output is correct
9 Correct 1937 ms 514008 KB Output is correct
10 Correct 1902 ms 514100 KB Output is correct
11 Correct 373 ms 336364 KB Output is correct
12 Correct 642 ms 374380 KB Output is correct
13 Correct 672 ms 379756 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 293868 KB Output is correct
2 Correct 207 ms 293996 KB Output is correct
3 Correct 199 ms 293996 KB Output is correct
4 Correct 200 ms 293996 KB Output is correct
5 Correct 208 ms 293868 KB Output is correct
6 Correct 202 ms 293996 KB Output is correct
7 Correct 215 ms 293868 KB Output is correct
8 Correct 208 ms 293868 KB Output is correct
9 Correct 205 ms 293996 KB Output is correct
10 Correct 203 ms 293868 KB Output is correct
11 Correct 203 ms 293868 KB Output is correct
12 Correct 204 ms 293956 KB Output is correct
13 Correct 210 ms 293996 KB Output is correct
14 Correct 197 ms 293868 KB Output is correct
15 Correct 204 ms 293868 KB Output is correct
16 Correct 201 ms 293868 KB Output is correct
17 Correct 205 ms 294636 KB Output is correct
18 Correct 203 ms 294508 KB Output is correct
19 Correct 225 ms 294508 KB Output is correct
20 Correct 210 ms 294124 KB Output is correct
21 Correct 202 ms 294380 KB Output is correct
22 Correct 204 ms 294252 KB Output is correct
23 Correct 202 ms 294252 KB Output is correct
24 Correct 202 ms 294124 KB Output is correct
25 Correct 221 ms 297700 KB Output is correct
26 Correct 216 ms 297764 KB Output is correct
27 Correct 218 ms 297700 KB Output is correct
28 Correct 218 ms 295632 KB Output is correct
29 Correct 219 ms 296632 KB Output is correct
30 Correct 227 ms 296684 KB Output is correct
31 Correct 230 ms 296556 KB Output is correct
32 Correct 221 ms 296428 KB Output is correct
33 Correct 337 ms 320820 KB Output is correct
34 Correct 311 ms 315988 KB Output is correct
35 Correct 338 ms 315988 KB Output is correct
36 Correct 284 ms 311128 KB Output is correct
37 Correct 489 ms 341700 KB Output is correct
38 Correct 452 ms 341700 KB Output is correct
39 Correct 459 ms 341700 KB Output is correct
40 Correct 447 ms 338500 KB Output is correct
41 Correct 321 ms 310240 KB Output is correct
42 Correct 342 ms 314332 KB Output is correct
43 Correct 513 ms 328936 KB Output is correct
44 Correct 538 ms 329036 KB Output is correct
45 Correct 357 ms 311520 KB Output is correct
46 Correct 371 ms 311264 KB Output is correct
47 Correct 500 ms 326604 KB Output is correct
48 Correct 491 ms 326732 KB Output is correct
49 Correct 203 ms 294252 KB Output is correct
50 Correct 201 ms 294124 KB Output is correct
51 Correct 202 ms 293996 KB Output is correct
52 Correct 212 ms 293912 KB Output is correct
53 Correct 207 ms 294124 KB Output is correct
54 Correct 201 ms 294124 KB Output is correct
55 Correct 216 ms 294124 KB Output is correct
56 Correct 203 ms 293996 KB Output is correct
57 Correct 199 ms 293996 KB Output is correct
58 Correct 217 ms 293868 KB Output is correct
59 Correct 201 ms 293868 KB Output is correct
60 Correct 203 ms 293924 KB Output is correct
61 Correct 935 ms 389544 KB Output is correct
62 Correct 1856 ms 513020 KB Output is correct
63 Correct 1937 ms 514008 KB Output is correct
64 Correct 1902 ms 514100 KB Output is correct
65 Correct 373 ms 336364 KB Output is correct
66 Correct 642 ms 374380 KB Output is correct
67 Correct 672 ms 379756 KB Output is correct
68 Correct 202 ms 293868 KB Output is correct
69 Correct 204 ms 293868 KB Output is correct
70 Correct 213 ms 293868 KB Output is correct
71 Correct 197 ms 293868 KB Output is correct
72 Correct 205 ms 293868 KB Output is correct
73 Correct 2540 ms 683328 KB Output is correct
74 Correct 1903 ms 616372 KB Output is correct
75 Correct 2412 ms 616192 KB Output is correct
76 Correct 1447 ms 549392 KB Output is correct
77 Correct 4678 ms 953156 KB Output is correct
78 Correct 2876 ms 576096 KB Output is correct
79 Correct 3035 ms 601500 KB Output is correct
80 Correct 4795 ms 764940 KB Output is correct
81 Correct 2921 ms 593864 KB Output is correct
82 Correct 3929 ms 694344 KB Output is correct
83 Correct 4964 ms 794372 KB Output is correct
84 Correct 2753 ms 569360 KB Output is correct
85 Correct 4600 ms 768036 KB Output is correct
86 Correct 4518 ms 753628 KB Output is correct
87 Correct 2775 ms 689736 KB Output is correct
88 Correct 4623 ms 944660 KB Output is correct
89 Correct 4792 ms 950292 KB Output is correct
90 Correct 4626 ms 951760 KB Output is correct