# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
223024 |
2020-04-14T13:46:09 Z |
abeker |
Rectangles (IOI19_rect) |
C++17 |
|
4740 ms |
961212 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <short, short> pii;
const int MAXN = 2.5e3 + 5;
short foo[MAXN];
vector <short> rows[MAXN][MAXN], cols[MAXN][MAXN];
vector <pii> in[MAXN][MAXN], out[MAXN][MAXN];
int f[MAXN][MAXN];
void update(int r, int x, int val) {
for (x++; x < MAXN; x += x & -x)
f[r][x] += val;
}
int get(int r, int x) {
int res = 0;
for (x++; x; x -= x & -x)
res += f[r][x];
return res;
}
void find_pairs(const vector <int> &arr, vector <short> ref[MAXN][MAXN], int idx) {
int n = arr.size(), sz = 0;
for (int i = 0; i < n; i++) {
while (sz && arr[foo[sz - 1]] < arr[i])
sz--;
if (sz && foo[sz - 1] < i - 1)
ref[foo[sz - 1]][i].push_back(idx);
foo[sz++] = i;
}
sz = 0;
for (int i = n - 1; i >= 0; i--) {
while (sz && arr[foo[sz - 1]] < arr[i])
sz--;
if (sz && arr[foo[sz - 1]] > arr[i] && foo[sz - 1] > i + 1)
ref[i][foo[sz - 1]].push_back(idx);
foo[sz++] = i;
}
}
ll count_rectangles(vector <vector <int>> a) {
int N = a.size();
int M = a[0].size();
for (int i = 0; i < N; i++)
find_pairs(a[i], rows, i);
for (int j = 0; j < M; j++) {
vector <int> curr;
for (int i = 0; i < N; i++)
curr.push_back(a[i][j]);
find_pairs(curr, cols, j);
}
for (int i = 0; i < N; i++)
for (int j = i + 2; j < N; j++) {
int lst = 0;
int sz = cols[i][j].size();
for (int k = 0; k < sz; k++)
if (k == sz - 1 || cols[i][j][k + 1] > cols[i][j][k] + 1) {
int lo = max(cols[i][j][lst] - 1, 0);
int hi = min(cols[i][j][k] + 1, M - 1);
for (int l = lo; l <= hi; l++) {
in[l][lo].push_back({i, j});
out[l][hi].push_back({i, j});
}
lst = k + 1;
}
}
ll sol = 0;
for (int i = 0; i < M; i++)
for (int j = 0; j < M; j++) {
for (auto it : in[i][j])
update(it.first, it.second, 1);
if (j > i + 1) {
int lst = 0;
int sz = rows[i][j].size();
for (int k = 0; k < sz; k++)
if (k == sz - 1 || rows[i][j][k + 1] > rows[i][j][k] + 1) {
int lo = max(rows[i][j][lst] - 1, 0);
int hi = min(rows[i][j][k] + 1, N - 1);
for (int l = lo; l <= hi; l++)
sol += get(l, hi) - get(l, lo - 1);
lst = k + 1;
}
}
for (auto it : out[i][j])
update(it.first, it.second, -1);
}
return sol;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
354 ms |
589948 KB |
Output is correct |
2 |
Correct |
351 ms |
590072 KB |
Output is correct |
3 |
Correct |
359 ms |
590200 KB |
Output is correct |
4 |
Correct |
358 ms |
590072 KB |
Output is correct |
5 |
Correct |
354 ms |
589896 KB |
Output is correct |
6 |
Correct |
355 ms |
590160 KB |
Output is correct |
7 |
Correct |
349 ms |
590072 KB |
Output is correct |
8 |
Correct |
361 ms |
589816 KB |
Output is correct |
9 |
Correct |
346 ms |
590200 KB |
Output is correct |
10 |
Correct |
350 ms |
590072 KB |
Output is correct |
11 |
Correct |
351 ms |
590072 KB |
Output is correct |
12 |
Correct |
355 ms |
590120 KB |
Output is correct |
13 |
Correct |
355 ms |
589688 KB |
Output is correct |
14 |
Correct |
350 ms |
589916 KB |
Output is correct |
15 |
Correct |
348 ms |
589688 KB |
Output is correct |
16 |
Correct |
359 ms |
589816 KB |
Output is correct |
17 |
Correct |
360 ms |
589816 KB |
Output is correct |
18 |
Correct |
348 ms |
589944 KB |
Output is correct |
19 |
Correct |
353 ms |
590072 KB |
Output is correct |
20 |
Correct |
357 ms |
589816 KB |
Output is correct |
21 |
Correct |
346 ms |
589816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
354 ms |
589948 KB |
Output is correct |
2 |
Correct |
351 ms |
590072 KB |
Output is correct |
3 |
Correct |
359 ms |
590200 KB |
Output is correct |
4 |
Correct |
358 ms |
590072 KB |
Output is correct |
5 |
Correct |
354 ms |
589896 KB |
Output is correct |
6 |
Correct |
355 ms |
590160 KB |
Output is correct |
7 |
Correct |
349 ms |
590072 KB |
Output is correct |
8 |
Correct |
361 ms |
589816 KB |
Output is correct |
9 |
Correct |
346 ms |
590200 KB |
Output is correct |
10 |
Correct |
350 ms |
590072 KB |
Output is correct |
11 |
Correct |
351 ms |
590072 KB |
Output is correct |
12 |
Correct |
355 ms |
590120 KB |
Output is correct |
13 |
Correct |
355 ms |
589688 KB |
Output is correct |
14 |
Correct |
350 ms |
589916 KB |
Output is correct |
15 |
Correct |
348 ms |
589688 KB |
Output is correct |
16 |
Correct |
359 ms |
589816 KB |
Output is correct |
17 |
Correct |
356 ms |
590840 KB |
Output is correct |
18 |
Correct |
352 ms |
590716 KB |
Output is correct |
19 |
Correct |
359 ms |
590712 KB |
Output is correct |
20 |
Correct |
354 ms |
590712 KB |
Output is correct |
21 |
Correct |
360 ms |
590840 KB |
Output is correct |
22 |
Correct |
364 ms |
590872 KB |
Output is correct |
23 |
Correct |
353 ms |
590840 KB |
Output is correct |
24 |
Correct |
377 ms |
590712 KB |
Output is correct |
25 |
Correct |
360 ms |
589816 KB |
Output is correct |
26 |
Correct |
348 ms |
589944 KB |
Output is correct |
27 |
Correct |
353 ms |
590072 KB |
Output is correct |
28 |
Correct |
357 ms |
589816 KB |
Output is correct |
29 |
Correct |
346 ms |
589816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
354 ms |
589948 KB |
Output is correct |
2 |
Correct |
351 ms |
590072 KB |
Output is correct |
3 |
Correct |
359 ms |
590200 KB |
Output is correct |
4 |
Correct |
358 ms |
590072 KB |
Output is correct |
5 |
Correct |
354 ms |
589896 KB |
Output is correct |
6 |
Correct |
355 ms |
590160 KB |
Output is correct |
7 |
Correct |
349 ms |
590072 KB |
Output is correct |
8 |
Correct |
361 ms |
589816 KB |
Output is correct |
9 |
Correct |
346 ms |
590200 KB |
Output is correct |
10 |
Correct |
350 ms |
590072 KB |
Output is correct |
11 |
Correct |
351 ms |
590072 KB |
Output is correct |
12 |
Correct |
355 ms |
590120 KB |
Output is correct |
13 |
Correct |
355 ms |
589688 KB |
Output is correct |
14 |
Correct |
350 ms |
589916 KB |
Output is correct |
15 |
Correct |
348 ms |
589688 KB |
Output is correct |
16 |
Correct |
359 ms |
589816 KB |
Output is correct |
17 |
Correct |
356 ms |
590840 KB |
Output is correct |
18 |
Correct |
352 ms |
590716 KB |
Output is correct |
19 |
Correct |
359 ms |
590712 KB |
Output is correct |
20 |
Correct |
354 ms |
590712 KB |
Output is correct |
21 |
Correct |
360 ms |
590840 KB |
Output is correct |
22 |
Correct |
364 ms |
590872 KB |
Output is correct |
23 |
Correct |
353 ms |
590840 KB |
Output is correct |
24 |
Correct |
377 ms |
590712 KB |
Output is correct |
25 |
Correct |
360 ms |
593016 KB |
Output is correct |
26 |
Correct |
390 ms |
592892 KB |
Output is correct |
27 |
Correct |
364 ms |
592888 KB |
Output is correct |
28 |
Correct |
387 ms |
592956 KB |
Output is correct |
29 |
Correct |
375 ms |
594168 KB |
Output is correct |
30 |
Correct |
372 ms |
594404 KB |
Output is correct |
31 |
Correct |
374 ms |
593784 KB |
Output is correct |
32 |
Correct |
379 ms |
594068 KB |
Output is correct |
33 |
Correct |
360 ms |
589816 KB |
Output is correct |
34 |
Correct |
348 ms |
589944 KB |
Output is correct |
35 |
Correct |
353 ms |
590072 KB |
Output is correct |
36 |
Correct |
357 ms |
589816 KB |
Output is correct |
37 |
Correct |
346 ms |
589816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
354 ms |
589948 KB |
Output is correct |
2 |
Correct |
351 ms |
590072 KB |
Output is correct |
3 |
Correct |
359 ms |
590200 KB |
Output is correct |
4 |
Correct |
358 ms |
590072 KB |
Output is correct |
5 |
Correct |
354 ms |
589896 KB |
Output is correct |
6 |
Correct |
355 ms |
590160 KB |
Output is correct |
7 |
Correct |
349 ms |
590072 KB |
Output is correct |
8 |
Correct |
361 ms |
589816 KB |
Output is correct |
9 |
Correct |
346 ms |
590200 KB |
Output is correct |
10 |
Correct |
350 ms |
590072 KB |
Output is correct |
11 |
Correct |
351 ms |
590072 KB |
Output is correct |
12 |
Correct |
355 ms |
590120 KB |
Output is correct |
13 |
Correct |
355 ms |
589688 KB |
Output is correct |
14 |
Correct |
350 ms |
589916 KB |
Output is correct |
15 |
Correct |
348 ms |
589688 KB |
Output is correct |
16 |
Correct |
359 ms |
589816 KB |
Output is correct |
17 |
Correct |
356 ms |
590840 KB |
Output is correct |
18 |
Correct |
352 ms |
590716 KB |
Output is correct |
19 |
Correct |
359 ms |
590712 KB |
Output is correct |
20 |
Correct |
354 ms |
590712 KB |
Output is correct |
21 |
Correct |
360 ms |
590840 KB |
Output is correct |
22 |
Correct |
364 ms |
590872 KB |
Output is correct |
23 |
Correct |
353 ms |
590840 KB |
Output is correct |
24 |
Correct |
377 ms |
590712 KB |
Output is correct |
25 |
Correct |
360 ms |
593016 KB |
Output is correct |
26 |
Correct |
390 ms |
592892 KB |
Output is correct |
27 |
Correct |
364 ms |
592888 KB |
Output is correct |
28 |
Correct |
387 ms |
592956 KB |
Output is correct |
29 |
Correct |
375 ms |
594168 KB |
Output is correct |
30 |
Correct |
372 ms |
594404 KB |
Output is correct |
31 |
Correct |
374 ms |
593784 KB |
Output is correct |
32 |
Correct |
379 ms |
594068 KB |
Output is correct |
33 |
Correct |
529 ms |
625784 KB |
Output is correct |
34 |
Correct |
499 ms |
625784 KB |
Output is correct |
35 |
Correct |
494 ms |
625812 KB |
Output is correct |
36 |
Correct |
477 ms |
625784 KB |
Output is correct |
37 |
Correct |
459 ms |
610040 KB |
Output is correct |
38 |
Correct |
460 ms |
610040 KB |
Output is correct |
39 |
Correct |
496 ms |
610040 KB |
Output is correct |
40 |
Correct |
465 ms |
609500 KB |
Output is correct |
41 |
Correct |
438 ms |
606968 KB |
Output is correct |
42 |
Correct |
480 ms |
607792 KB |
Output is correct |
43 |
Correct |
620 ms |
626008 KB |
Output is correct |
44 |
Correct |
621 ms |
626296 KB |
Output is correct |
45 |
Correct |
483 ms |
611960 KB |
Output is correct |
46 |
Correct |
491 ms |
608760 KB |
Output is correct |
47 |
Correct |
573 ms |
616056 KB |
Output is correct |
48 |
Correct |
595 ms |
615996 KB |
Output is correct |
49 |
Correct |
360 ms |
589816 KB |
Output is correct |
50 |
Correct |
348 ms |
589944 KB |
Output is correct |
51 |
Correct |
353 ms |
590072 KB |
Output is correct |
52 |
Correct |
357 ms |
589816 KB |
Output is correct |
53 |
Correct |
346 ms |
589816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
385 ms |
590200 KB |
Output is correct |
2 |
Correct |
376 ms |
590056 KB |
Output is correct |
3 |
Correct |
375 ms |
589816 KB |
Output is correct |
4 |
Correct |
350 ms |
589724 KB |
Output is correct |
5 |
Correct |
383 ms |
590200 KB |
Output is correct |
6 |
Correct |
392 ms |
590328 KB |
Output is correct |
7 |
Correct |
378 ms |
590328 KB |
Output is correct |
8 |
Correct |
380 ms |
590200 KB |
Output is correct |
9 |
Correct |
372 ms |
590200 KB |
Output is correct |
10 |
Correct |
369 ms |
589944 KB |
Output is correct |
11 |
Correct |
383 ms |
589944 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
354 ms |
589792 KB |
Output is correct |
2 |
Correct |
994 ms |
662392 KB |
Output is correct |
3 |
Correct |
1717 ms |
736652 KB |
Output is correct |
4 |
Correct |
1791 ms |
737016 KB |
Output is correct |
5 |
Correct |
1789 ms |
737016 KB |
Output is correct |
6 |
Correct |
490 ms |
614908 KB |
Output is correct |
7 |
Correct |
573 ms |
636792 KB |
Output is correct |
8 |
Correct |
588 ms |
639968 KB |
Output is correct |
9 |
Correct |
360 ms |
589816 KB |
Output is correct |
10 |
Correct |
348 ms |
589944 KB |
Output is correct |
11 |
Correct |
353 ms |
590072 KB |
Output is correct |
12 |
Correct |
357 ms |
589816 KB |
Output is correct |
13 |
Correct |
346 ms |
589816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
354 ms |
589948 KB |
Output is correct |
2 |
Correct |
351 ms |
590072 KB |
Output is correct |
3 |
Correct |
359 ms |
590200 KB |
Output is correct |
4 |
Correct |
358 ms |
590072 KB |
Output is correct |
5 |
Correct |
354 ms |
589896 KB |
Output is correct |
6 |
Correct |
355 ms |
590160 KB |
Output is correct |
7 |
Correct |
349 ms |
590072 KB |
Output is correct |
8 |
Correct |
361 ms |
589816 KB |
Output is correct |
9 |
Correct |
346 ms |
590200 KB |
Output is correct |
10 |
Correct |
350 ms |
590072 KB |
Output is correct |
11 |
Correct |
351 ms |
590072 KB |
Output is correct |
12 |
Correct |
355 ms |
590120 KB |
Output is correct |
13 |
Correct |
355 ms |
589688 KB |
Output is correct |
14 |
Correct |
350 ms |
589916 KB |
Output is correct |
15 |
Correct |
348 ms |
589688 KB |
Output is correct |
16 |
Correct |
359 ms |
589816 KB |
Output is correct |
17 |
Correct |
356 ms |
590840 KB |
Output is correct |
18 |
Correct |
352 ms |
590716 KB |
Output is correct |
19 |
Correct |
359 ms |
590712 KB |
Output is correct |
20 |
Correct |
354 ms |
590712 KB |
Output is correct |
21 |
Correct |
360 ms |
590840 KB |
Output is correct |
22 |
Correct |
364 ms |
590872 KB |
Output is correct |
23 |
Correct |
353 ms |
590840 KB |
Output is correct |
24 |
Correct |
377 ms |
590712 KB |
Output is correct |
25 |
Correct |
360 ms |
593016 KB |
Output is correct |
26 |
Correct |
390 ms |
592892 KB |
Output is correct |
27 |
Correct |
364 ms |
592888 KB |
Output is correct |
28 |
Correct |
387 ms |
592956 KB |
Output is correct |
29 |
Correct |
375 ms |
594168 KB |
Output is correct |
30 |
Correct |
372 ms |
594404 KB |
Output is correct |
31 |
Correct |
374 ms |
593784 KB |
Output is correct |
32 |
Correct |
379 ms |
594068 KB |
Output is correct |
33 |
Correct |
529 ms |
625784 KB |
Output is correct |
34 |
Correct |
499 ms |
625784 KB |
Output is correct |
35 |
Correct |
494 ms |
625812 KB |
Output is correct |
36 |
Correct |
477 ms |
625784 KB |
Output is correct |
37 |
Correct |
459 ms |
610040 KB |
Output is correct |
38 |
Correct |
460 ms |
610040 KB |
Output is correct |
39 |
Correct |
496 ms |
610040 KB |
Output is correct |
40 |
Correct |
465 ms |
609500 KB |
Output is correct |
41 |
Correct |
438 ms |
606968 KB |
Output is correct |
42 |
Correct |
480 ms |
607792 KB |
Output is correct |
43 |
Correct |
620 ms |
626008 KB |
Output is correct |
44 |
Correct |
621 ms |
626296 KB |
Output is correct |
45 |
Correct |
483 ms |
611960 KB |
Output is correct |
46 |
Correct |
491 ms |
608760 KB |
Output is correct |
47 |
Correct |
573 ms |
616056 KB |
Output is correct |
48 |
Correct |
595 ms |
615996 KB |
Output is correct |
49 |
Correct |
385 ms |
590200 KB |
Output is correct |
50 |
Correct |
376 ms |
590056 KB |
Output is correct |
51 |
Correct |
375 ms |
589816 KB |
Output is correct |
52 |
Correct |
350 ms |
589724 KB |
Output is correct |
53 |
Correct |
383 ms |
590200 KB |
Output is correct |
54 |
Correct |
392 ms |
590328 KB |
Output is correct |
55 |
Correct |
378 ms |
590328 KB |
Output is correct |
56 |
Correct |
380 ms |
590200 KB |
Output is correct |
57 |
Correct |
372 ms |
590200 KB |
Output is correct |
58 |
Correct |
369 ms |
589944 KB |
Output is correct |
59 |
Correct |
383 ms |
589944 KB |
Output is correct |
60 |
Correct |
354 ms |
589792 KB |
Output is correct |
61 |
Correct |
994 ms |
662392 KB |
Output is correct |
62 |
Correct |
1717 ms |
736652 KB |
Output is correct |
63 |
Correct |
1791 ms |
737016 KB |
Output is correct |
64 |
Correct |
1789 ms |
737016 KB |
Output is correct |
65 |
Correct |
490 ms |
614908 KB |
Output is correct |
66 |
Correct |
573 ms |
636792 KB |
Output is correct |
67 |
Correct |
588 ms |
639968 KB |
Output is correct |
68 |
Correct |
3119 ms |
960508 KB |
Output is correct |
69 |
Correct |
2609 ms |
961212 KB |
Output is correct |
70 |
Correct |
2279 ms |
957176 KB |
Output is correct |
71 |
Correct |
1796 ms |
957176 KB |
Output is correct |
72 |
Correct |
2066 ms |
764792 KB |
Output is correct |
73 |
Correct |
2769 ms |
804004 KB |
Output is correct |
74 |
Correct |
2927 ms |
828152 KB |
Output is correct |
75 |
Correct |
4553 ms |
913532 KB |
Output is correct |
76 |
Correct |
2911 ms |
803784 KB |
Output is correct |
77 |
Correct |
3705 ms |
885060 KB |
Output is correct |
78 |
Correct |
4740 ms |
952052 KB |
Output is correct |
79 |
Correct |
2521 ms |
761464 KB |
Output is correct |
80 |
Correct |
4040 ms |
889360 KB |
Output is correct |
81 |
Correct |
3946 ms |
885076 KB |
Output is correct |
82 |
Correct |
1344 ms |
725060 KB |
Output is correct |
83 |
Correct |
2049 ms |
811788 KB |
Output is correct |
84 |
Correct |
1998 ms |
811896 KB |
Output is correct |
85 |
Correct |
2017 ms |
811888 KB |
Output is correct |
86 |
Correct |
360 ms |
589816 KB |
Output is correct |
87 |
Correct |
348 ms |
589944 KB |
Output is correct |
88 |
Correct |
353 ms |
590072 KB |
Output is correct |
89 |
Correct |
357 ms |
589816 KB |
Output is correct |
90 |
Correct |
346 ms |
589816 KB |
Output is correct |