# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
256809 |
2020-08-03T08:49:53 Z |
atoiz |
Rectangles (IOI19_rect) |
C++14 |
|
3219 ms |
837336 KB |
#include "rect.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define x first
#define y second
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORA(i, a) for (auto &i : a)
#define FORB(i, a, b) for (int i = a; i >= b; --i)
const int MAXN = 2505;
int R, C, A[MAXN][MAXN];
int prv[MAXN], nxt[MAXN], last[MAXN][MAXN], endp[MAXN][MAXN];
vector<pii> boundLR[MAXN][MAXN], boundUD[MAXN][MAXN];
int bit[MAXN];
void modify(int i, int x) {
for (; i < MAXN; i += (i & (-i))) bit[i] += x;
}
int get(int i) {
int ans = 0;
for (; i > 0; i -= i & (-i)) ans += bit[i];
return ans;
}
ll count_rectangles(vector<vector<int>> _A) {
R = (int) _A.size(), C = (int) _A[0].size();
FOR(i, 1, R) FOR(j, 1, C) A[i][j] = _A[i - 1][j - 1];
// for each row
FOR(l, 1, C) FOR(r, l + 2, C) last[l][r] = -1;
FORB(r, R, 2) {
prv[1] = 0, nxt[C] = C + 1;
FOR(c, 2, C) for (prv[c] = c - 1; prv[c] > 0 && A[r][prv[c]] <= A[r][c]; prv[c] = prv[prv[c]]);
FORB(c, C - 1, 1) for (nxt[c] = c + 1; nxt[c] <= C && A[r][nxt[c]] <= A[r][c]; nxt[c] = nxt[nxt[c]]);
FOR(c, 1, C) if (1 <= prv[c] && nxt[c] <= C) {
int c0 = prv[c], c1 = nxt[c];
if (last[c0][c1] == r) continue;
if (last[c0][c1] != r + 1) endp[c0][c1] = r + 1;
last[c0][c1] = r;
boundLR[r - 1][c0].emplace_back(endp[c0][c1], c1);
}
}
// for each col
FOR(r0, 1, R) FOR(r1, r0 + 2, R) last[r0][r1] = -1;
FORB(c, C, 2) {
prv[1] = 0, nxt[R] = R + 1;
FOR(r, 2, R) for (prv[r] = r - 1; prv[r] >= 1 && A[prv[r]][c] <= A[r][c]; prv[r] = prv[prv[r]]);
FORB(r, R - 1, 1) for (nxt[r] = r + 1; nxt[r] <= R && A[nxt[r]][c] <= A[r][c]; nxt[r] = nxt[nxt[r]]);
FOR(r, 1, R) if (1 <= prv[r] && nxt[r] <= R) {
int r0 = prv[r], r1 = nxt[r];
if (last[r0][r1] == c) continue;
if (last[r0][r1] != c + 1) endp[r0][r1] = c + 1;
last[r0][r1] = c;
boundUD[r0][c - 1].emplace_back(r1, endp[r0][r1]);
}
}
ll ans = 0;
FOR(rootR, 1, R - 2) FOR(rootC, 1, C - 2) if (!boundLR[rootR][rootC].empty() && !boundUD[rootR][rootC].empty()) {
auto &curLR = boundLR[rootR][rootC], &curUD = boundUD[rootR][rootC];
sort(curLR.begin(), curLR.end()), sort(curUD.begin(), curUD.end());
auto itLR = curLR.begin();
auto itUD = curUD.begin();
while (itLR != curLR.end() || itUD != curUD.end()) {
if (itLR != curLR.end() && (itUD == curUD.end() || itLR->x < itUD->x)) {
ans += get((C + 5) - (itLR++)->second);
} else {
modify((C + 5) - (itUD++)->second, 1);
}
}
for (auto p : curUD) modify((C + 5) - p.second, -1);
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
161 ms |
295160 KB |
Output is correct |
2 |
Correct |
169 ms |
295416 KB |
Output is correct |
3 |
Correct |
181 ms |
295540 KB |
Output is correct |
4 |
Correct |
178 ms |
295544 KB |
Output is correct |
5 |
Correct |
169 ms |
295288 KB |
Output is correct |
6 |
Correct |
169 ms |
295416 KB |
Output is correct |
7 |
Correct |
173 ms |
295416 KB |
Output is correct |
8 |
Correct |
179 ms |
295336 KB |
Output is correct |
9 |
Correct |
177 ms |
295476 KB |
Output is correct |
10 |
Correct |
172 ms |
295412 KB |
Output is correct |
11 |
Correct |
179 ms |
295544 KB |
Output is correct |
12 |
Correct |
181 ms |
295368 KB |
Output is correct |
13 |
Correct |
172 ms |
295032 KB |
Output is correct |
14 |
Correct |
170 ms |
295160 KB |
Output is correct |
15 |
Correct |
179 ms |
295288 KB |
Output is correct |
16 |
Correct |
186 ms |
295032 KB |
Output is correct |
17 |
Correct |
184 ms |
295032 KB |
Output is correct |
18 |
Correct |
168 ms |
295056 KB |
Output is correct |
19 |
Correct |
184 ms |
295416 KB |
Output is correct |
20 |
Correct |
186 ms |
295288 KB |
Output is correct |
21 |
Correct |
169 ms |
295108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
161 ms |
295160 KB |
Output is correct |
2 |
Correct |
169 ms |
295416 KB |
Output is correct |
3 |
Correct |
181 ms |
295540 KB |
Output is correct |
4 |
Correct |
178 ms |
295544 KB |
Output is correct |
5 |
Correct |
169 ms |
295288 KB |
Output is correct |
6 |
Correct |
169 ms |
295416 KB |
Output is correct |
7 |
Correct |
173 ms |
295416 KB |
Output is correct |
8 |
Correct |
179 ms |
295336 KB |
Output is correct |
9 |
Correct |
177 ms |
295476 KB |
Output is correct |
10 |
Correct |
172 ms |
295412 KB |
Output is correct |
11 |
Correct |
179 ms |
295544 KB |
Output is correct |
12 |
Correct |
181 ms |
295368 KB |
Output is correct |
13 |
Correct |
172 ms |
295032 KB |
Output is correct |
14 |
Correct |
170 ms |
295160 KB |
Output is correct |
15 |
Correct |
179 ms |
295288 KB |
Output is correct |
16 |
Correct |
186 ms |
295032 KB |
Output is correct |
17 |
Correct |
166 ms |
296440 KB |
Output is correct |
18 |
Correct |
173 ms |
296568 KB |
Output is correct |
19 |
Correct |
179 ms |
296440 KB |
Output is correct |
20 |
Correct |
170 ms |
296184 KB |
Output is correct |
21 |
Correct |
176 ms |
296312 KB |
Output is correct |
22 |
Correct |
171 ms |
296312 KB |
Output is correct |
23 |
Correct |
164 ms |
296344 KB |
Output is correct |
24 |
Correct |
176 ms |
296184 KB |
Output is correct |
25 |
Correct |
184 ms |
295032 KB |
Output is correct |
26 |
Correct |
168 ms |
295056 KB |
Output is correct |
27 |
Correct |
184 ms |
295416 KB |
Output is correct |
28 |
Correct |
186 ms |
295288 KB |
Output is correct |
29 |
Correct |
169 ms |
295108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
161 ms |
295160 KB |
Output is correct |
2 |
Correct |
169 ms |
295416 KB |
Output is correct |
3 |
Correct |
181 ms |
295540 KB |
Output is correct |
4 |
Correct |
178 ms |
295544 KB |
Output is correct |
5 |
Correct |
169 ms |
295288 KB |
Output is correct |
6 |
Correct |
169 ms |
295416 KB |
Output is correct |
7 |
Correct |
173 ms |
295416 KB |
Output is correct |
8 |
Correct |
179 ms |
295336 KB |
Output is correct |
9 |
Correct |
177 ms |
295476 KB |
Output is correct |
10 |
Correct |
172 ms |
295412 KB |
Output is correct |
11 |
Correct |
179 ms |
295544 KB |
Output is correct |
12 |
Correct |
181 ms |
295368 KB |
Output is correct |
13 |
Correct |
172 ms |
295032 KB |
Output is correct |
14 |
Correct |
170 ms |
295160 KB |
Output is correct |
15 |
Correct |
179 ms |
295288 KB |
Output is correct |
16 |
Correct |
186 ms |
295032 KB |
Output is correct |
17 |
Correct |
166 ms |
296440 KB |
Output is correct |
18 |
Correct |
173 ms |
296568 KB |
Output is correct |
19 |
Correct |
179 ms |
296440 KB |
Output is correct |
20 |
Correct |
170 ms |
296184 KB |
Output is correct |
21 |
Correct |
176 ms |
296312 KB |
Output is correct |
22 |
Correct |
171 ms |
296312 KB |
Output is correct |
23 |
Correct |
164 ms |
296344 KB |
Output is correct |
24 |
Correct |
176 ms |
296184 KB |
Output is correct |
25 |
Correct |
179 ms |
300712 KB |
Output is correct |
26 |
Correct |
178 ms |
300664 KB |
Output is correct |
27 |
Correct |
188 ms |
300764 KB |
Output is correct |
28 |
Correct |
174 ms |
298872 KB |
Output is correct |
29 |
Correct |
178 ms |
299640 KB |
Output is correct |
30 |
Correct |
173 ms |
299768 KB |
Output is correct |
31 |
Correct |
182 ms |
299640 KB |
Output is correct |
32 |
Correct |
174 ms |
299640 KB |
Output is correct |
33 |
Correct |
184 ms |
295032 KB |
Output is correct |
34 |
Correct |
168 ms |
295056 KB |
Output is correct |
35 |
Correct |
184 ms |
295416 KB |
Output is correct |
36 |
Correct |
186 ms |
295288 KB |
Output is correct |
37 |
Correct |
169 ms |
295108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
161 ms |
295160 KB |
Output is correct |
2 |
Correct |
169 ms |
295416 KB |
Output is correct |
3 |
Correct |
181 ms |
295540 KB |
Output is correct |
4 |
Correct |
178 ms |
295544 KB |
Output is correct |
5 |
Correct |
169 ms |
295288 KB |
Output is correct |
6 |
Correct |
169 ms |
295416 KB |
Output is correct |
7 |
Correct |
173 ms |
295416 KB |
Output is correct |
8 |
Correct |
179 ms |
295336 KB |
Output is correct |
9 |
Correct |
177 ms |
295476 KB |
Output is correct |
10 |
Correct |
172 ms |
295412 KB |
Output is correct |
11 |
Correct |
179 ms |
295544 KB |
Output is correct |
12 |
Correct |
181 ms |
295368 KB |
Output is correct |
13 |
Correct |
172 ms |
295032 KB |
Output is correct |
14 |
Correct |
170 ms |
295160 KB |
Output is correct |
15 |
Correct |
179 ms |
295288 KB |
Output is correct |
16 |
Correct |
186 ms |
295032 KB |
Output is correct |
17 |
Correct |
166 ms |
296440 KB |
Output is correct |
18 |
Correct |
173 ms |
296568 KB |
Output is correct |
19 |
Correct |
179 ms |
296440 KB |
Output is correct |
20 |
Correct |
170 ms |
296184 KB |
Output is correct |
21 |
Correct |
176 ms |
296312 KB |
Output is correct |
22 |
Correct |
171 ms |
296312 KB |
Output is correct |
23 |
Correct |
164 ms |
296344 KB |
Output is correct |
24 |
Correct |
176 ms |
296184 KB |
Output is correct |
25 |
Correct |
179 ms |
300712 KB |
Output is correct |
26 |
Correct |
178 ms |
300664 KB |
Output is correct |
27 |
Correct |
188 ms |
300764 KB |
Output is correct |
28 |
Correct |
174 ms |
298872 KB |
Output is correct |
29 |
Correct |
178 ms |
299640 KB |
Output is correct |
30 |
Correct |
173 ms |
299768 KB |
Output is correct |
31 |
Correct |
182 ms |
299640 KB |
Output is correct |
32 |
Correct |
174 ms |
299640 KB |
Output is correct |
33 |
Correct |
261 ms |
329524 KB |
Output is correct |
34 |
Correct |
238 ms |
324856 KB |
Output is correct |
35 |
Correct |
237 ms |
324860 KB |
Output is correct |
36 |
Correct |
217 ms |
320120 KB |
Output is correct |
37 |
Correct |
333 ms |
344060 KB |
Output is correct |
38 |
Correct |
352 ms |
344024 KB |
Output is correct |
39 |
Correct |
336 ms |
344312 KB |
Output is correct |
40 |
Correct |
319 ms |
341752 KB |
Output is correct |
41 |
Correct |
248 ms |
318840 KB |
Output is correct |
42 |
Correct |
283 ms |
321400 KB |
Output is correct |
43 |
Correct |
336 ms |
330744 KB |
Output is correct |
44 |
Correct |
338 ms |
332920 KB |
Output is correct |
45 |
Correct |
256 ms |
318840 KB |
Output is correct |
46 |
Correct |
249 ms |
317560 KB |
Output is correct |
47 |
Correct |
337 ms |
329816 KB |
Output is correct |
48 |
Correct |
331 ms |
330904 KB |
Output is correct |
49 |
Correct |
184 ms |
295032 KB |
Output is correct |
50 |
Correct |
168 ms |
295056 KB |
Output is correct |
51 |
Correct |
184 ms |
295416 KB |
Output is correct |
52 |
Correct |
186 ms |
295288 KB |
Output is correct |
53 |
Correct |
169 ms |
295108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
325624 KB |
Output is correct |
2 |
Correct |
175 ms |
320468 KB |
Output is correct |
3 |
Correct |
175 ms |
315384 KB |
Output is correct |
4 |
Correct |
163 ms |
295032 KB |
Output is correct |
5 |
Correct |
184 ms |
323320 KB |
Output is correct |
6 |
Correct |
176 ms |
323212 KB |
Output is correct |
7 |
Correct |
178 ms |
323064 KB |
Output is correct |
8 |
Correct |
179 ms |
322552 KB |
Output is correct |
9 |
Correct |
177 ms |
322296 KB |
Output is correct |
10 |
Correct |
178 ms |
315256 KB |
Output is correct |
11 |
Correct |
179 ms |
320504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
168 ms |
295160 KB |
Output is correct |
2 |
Correct |
642 ms |
407576 KB |
Output is correct |
3 |
Correct |
1280 ms |
508036 KB |
Output is correct |
4 |
Correct |
1286 ms |
508964 KB |
Output is correct |
5 |
Correct |
1237 ms |
509044 KB |
Output is correct |
6 |
Correct |
297 ms |
357624 KB |
Output is correct |
7 |
Correct |
429 ms |
397304 KB |
Output is correct |
8 |
Correct |
446 ms |
401144 KB |
Output is correct |
9 |
Correct |
184 ms |
295032 KB |
Output is correct |
10 |
Correct |
168 ms |
295056 KB |
Output is correct |
11 |
Correct |
184 ms |
295416 KB |
Output is correct |
12 |
Correct |
186 ms |
295288 KB |
Output is correct |
13 |
Correct |
169 ms |
295108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
161 ms |
295160 KB |
Output is correct |
2 |
Correct |
169 ms |
295416 KB |
Output is correct |
3 |
Correct |
181 ms |
295540 KB |
Output is correct |
4 |
Correct |
178 ms |
295544 KB |
Output is correct |
5 |
Correct |
169 ms |
295288 KB |
Output is correct |
6 |
Correct |
169 ms |
295416 KB |
Output is correct |
7 |
Correct |
173 ms |
295416 KB |
Output is correct |
8 |
Correct |
179 ms |
295336 KB |
Output is correct |
9 |
Correct |
177 ms |
295476 KB |
Output is correct |
10 |
Correct |
172 ms |
295412 KB |
Output is correct |
11 |
Correct |
179 ms |
295544 KB |
Output is correct |
12 |
Correct |
181 ms |
295368 KB |
Output is correct |
13 |
Correct |
172 ms |
295032 KB |
Output is correct |
14 |
Correct |
170 ms |
295160 KB |
Output is correct |
15 |
Correct |
179 ms |
295288 KB |
Output is correct |
16 |
Correct |
186 ms |
295032 KB |
Output is correct |
17 |
Correct |
166 ms |
296440 KB |
Output is correct |
18 |
Correct |
173 ms |
296568 KB |
Output is correct |
19 |
Correct |
179 ms |
296440 KB |
Output is correct |
20 |
Correct |
170 ms |
296184 KB |
Output is correct |
21 |
Correct |
176 ms |
296312 KB |
Output is correct |
22 |
Correct |
171 ms |
296312 KB |
Output is correct |
23 |
Correct |
164 ms |
296344 KB |
Output is correct |
24 |
Correct |
176 ms |
296184 KB |
Output is correct |
25 |
Correct |
179 ms |
300712 KB |
Output is correct |
26 |
Correct |
178 ms |
300664 KB |
Output is correct |
27 |
Correct |
188 ms |
300764 KB |
Output is correct |
28 |
Correct |
174 ms |
298872 KB |
Output is correct |
29 |
Correct |
178 ms |
299640 KB |
Output is correct |
30 |
Correct |
173 ms |
299768 KB |
Output is correct |
31 |
Correct |
182 ms |
299640 KB |
Output is correct |
32 |
Correct |
174 ms |
299640 KB |
Output is correct |
33 |
Correct |
261 ms |
329524 KB |
Output is correct |
34 |
Correct |
238 ms |
324856 KB |
Output is correct |
35 |
Correct |
237 ms |
324860 KB |
Output is correct |
36 |
Correct |
217 ms |
320120 KB |
Output is correct |
37 |
Correct |
333 ms |
344060 KB |
Output is correct |
38 |
Correct |
352 ms |
344024 KB |
Output is correct |
39 |
Correct |
336 ms |
344312 KB |
Output is correct |
40 |
Correct |
319 ms |
341752 KB |
Output is correct |
41 |
Correct |
248 ms |
318840 KB |
Output is correct |
42 |
Correct |
283 ms |
321400 KB |
Output is correct |
43 |
Correct |
336 ms |
330744 KB |
Output is correct |
44 |
Correct |
338 ms |
332920 KB |
Output is correct |
45 |
Correct |
256 ms |
318840 KB |
Output is correct |
46 |
Correct |
249 ms |
317560 KB |
Output is correct |
47 |
Correct |
337 ms |
329816 KB |
Output is correct |
48 |
Correct |
331 ms |
330904 KB |
Output is correct |
49 |
Correct |
178 ms |
325624 KB |
Output is correct |
50 |
Correct |
175 ms |
320468 KB |
Output is correct |
51 |
Correct |
175 ms |
315384 KB |
Output is correct |
52 |
Correct |
163 ms |
295032 KB |
Output is correct |
53 |
Correct |
184 ms |
323320 KB |
Output is correct |
54 |
Correct |
176 ms |
323212 KB |
Output is correct |
55 |
Correct |
178 ms |
323064 KB |
Output is correct |
56 |
Correct |
179 ms |
322552 KB |
Output is correct |
57 |
Correct |
177 ms |
322296 KB |
Output is correct |
58 |
Correct |
178 ms |
315256 KB |
Output is correct |
59 |
Correct |
179 ms |
320504 KB |
Output is correct |
60 |
Correct |
168 ms |
295160 KB |
Output is correct |
61 |
Correct |
642 ms |
407576 KB |
Output is correct |
62 |
Correct |
1280 ms |
508036 KB |
Output is correct |
63 |
Correct |
1286 ms |
508964 KB |
Output is correct |
64 |
Correct |
1237 ms |
509044 KB |
Output is correct |
65 |
Correct |
297 ms |
357624 KB |
Output is correct |
66 |
Correct |
429 ms |
397304 KB |
Output is correct |
67 |
Correct |
446 ms |
401144 KB |
Output is correct |
68 |
Correct |
1501 ms |
650800 KB |
Output is correct |
69 |
Correct |
1486 ms |
584624 KB |
Output is correct |
70 |
Correct |
1090 ms |
584440 KB |
Output is correct |
71 |
Correct |
925 ms |
517368 KB |
Output is correct |
72 |
Correct |
3052 ms |
837336 KB |
Output is correct |
73 |
Correct |
1594 ms |
527864 KB |
Output is correct |
74 |
Correct |
1750 ms |
558200 KB |
Output is correct |
75 |
Correct |
2651 ms |
660788 KB |
Output is correct |
76 |
Correct |
1632 ms |
545912 KB |
Output is correct |
77 |
Correct |
2143 ms |
622712 KB |
Output is correct |
78 |
Correct |
2686 ms |
689296 KB |
Output is correct |
79 |
Correct |
1573 ms |
521168 KB |
Output is correct |
80 |
Correct |
2944 ms |
663516 KB |
Output is correct |
81 |
Correct |
2756 ms |
655312 KB |
Output is correct |
82 |
Correct |
1970 ms |
648256 KB |
Output is correct |
83 |
Correct |
3219 ms |
831064 KB |
Output is correct |
84 |
Correct |
3053 ms |
836856 KB |
Output is correct |
85 |
Correct |
3055 ms |
836312 KB |
Output is correct |
86 |
Correct |
184 ms |
295032 KB |
Output is correct |
87 |
Correct |
168 ms |
295056 KB |
Output is correct |
88 |
Correct |
184 ms |
295416 KB |
Output is correct |
89 |
Correct |
186 ms |
295288 KB |
Output is correct |
90 |
Correct |
169 ms |
295108 KB |
Output is correct |