# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
155689 |
2019-09-29T20:58:36 Z |
flashmt |
Rectangles (IOI19_rect) |
C++17 |
|
2037 ms |
273396 KB |
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> stRow, stCol, lastRow, lastCol, cntRow, cntCol;
int tree[2525];
void add(int x, int v)
{
for (int i = x; i <= 2500; i += i & -i)
tree[i] += v;
}
int get(int x)
{
int res = 0;
for (int i = x; i; i -= i & -i)
res += tree[i];
return res;
}
int solve(vector<pair<int, int>> &rows, vector<pair<int, int>> &cols)
{
int res = 0, i = 0;
sort(rows.begin(), rows.end());
for (auto u : rows)
{
while (i < cols.size() && cols[i].first <= u.first)
add(cols[i++].second, 1);
res += i - get(u.second - 1);
}
for (int j = 0; j < i; j++)
add(cols[j].second, -1);
return res;
}
long long count_rectangles(vector<vector<int>> a)
{
int m = a.size(), n = a[0].size();
stRow = vector<vector<int>>(m, vector<int>(1, 0));
stCol = vector<vector<int>>(n, vector<int>(1, 0));
lastRow = vector<vector<int>>(m, vector<int>(m, -1));
lastCol = vector<vector<int>>(n, vector<int>(n, -1));
cntRow = vector<vector<int>>(m, vector<int>(m, 0));
cntCol = vector<vector<int>>(n, vector<int>(n, 0));
long long ans = 0;
for (int i = 0; i < m - 1; i++)
for (int j = 0; j < n - 1; j++)
{
// row
int hasEqual = 0;
vector<pair<int, int>> cols;
while (!stRow[i].empty())
{
int k = stRow[i].back();
if (!hasEqual)
{
if (lastCol[k][j + 1] + 1 == i) cntCol[k][j + 1]++;
else cntCol[k][j + 1] = 1;
lastCol[k][j + 1] = i;
if (j > k)
cols.push_back({j - k, cntCol[k][j + 1]});
}
if (a[i][j + 1] < a[i][k])
break;
if (a[i][j + 1] == a[i][k])
hasEqual = 1;
stRow[i].pop_back();
}
stRow[i].push_back(j + 1);
// col
hasEqual = 0;
vector<pair<int, int>> rows;
while (!stCol[j].empty())
{
int k = stCol[j].back();
if (!hasEqual)
{
if (lastRow[k][i + 1] + 1 == j) cntRow[k][i + 1]++;
else cntRow[k][i + 1] = 1;
lastRow[k][i + 1] = j;
if (i > k)
rows.push_back({cntRow[k][i + 1], i - k});
}
if (a[i + 1][j] < a[k][j])
break;
if (a[i + 1][j] == a[k][j])
hasEqual = 1;
stCol[j].pop_back();
}
stCol[j].push_back(i + 1);
ans += solve(rows, cols);
}
return ans;
}
Compilation message
rect.cpp: In function 'int solve(std::vector<std::pair<int, int> >&, std::vector<std::pair<int, int> >&)':
rect.cpp:27:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i < cols.size() && cols[i].first <= u.first)
~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
504 KB |
Output is correct |
10 |
Correct |
2 ms |
380 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
396 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
256 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
380 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
504 KB |
Output is correct |
10 |
Correct |
2 ms |
380 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
396 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
3 ms |
632 KB |
Output is correct |
18 |
Correct |
3 ms |
632 KB |
Output is correct |
19 |
Correct |
3 ms |
632 KB |
Output is correct |
20 |
Correct |
3 ms |
632 KB |
Output is correct |
21 |
Correct |
4 ms |
504 KB |
Output is correct |
22 |
Correct |
4 ms |
504 KB |
Output is correct |
23 |
Correct |
3 ms |
504 KB |
Output is correct |
24 |
Correct |
3 ms |
504 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
256 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
380 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
504 KB |
Output is correct |
10 |
Correct |
2 ms |
380 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
396 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
3 ms |
632 KB |
Output is correct |
18 |
Correct |
3 ms |
632 KB |
Output is correct |
19 |
Correct |
3 ms |
632 KB |
Output is correct |
20 |
Correct |
3 ms |
632 KB |
Output is correct |
21 |
Correct |
4 ms |
504 KB |
Output is correct |
22 |
Correct |
4 ms |
504 KB |
Output is correct |
23 |
Correct |
3 ms |
504 KB |
Output is correct |
24 |
Correct |
3 ms |
504 KB |
Output is correct |
25 |
Correct |
8 ms |
1912 KB |
Output is correct |
26 |
Correct |
8 ms |
1916 KB |
Output is correct |
27 |
Correct |
9 ms |
1916 KB |
Output is correct |
28 |
Correct |
8 ms |
1400 KB |
Output is correct |
29 |
Correct |
11 ms |
1400 KB |
Output is correct |
30 |
Correct |
12 ms |
1528 KB |
Output is correct |
31 |
Correct |
12 ms |
1528 KB |
Output is correct |
32 |
Correct |
12 ms |
1528 KB |
Output is correct |
33 |
Correct |
2 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
256 KB |
Output is correct |
35 |
Correct |
2 ms |
376 KB |
Output is correct |
36 |
Correct |
2 ms |
380 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
504 KB |
Output is correct |
10 |
Correct |
2 ms |
380 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
396 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
3 ms |
632 KB |
Output is correct |
18 |
Correct |
3 ms |
632 KB |
Output is correct |
19 |
Correct |
3 ms |
632 KB |
Output is correct |
20 |
Correct |
3 ms |
632 KB |
Output is correct |
21 |
Correct |
4 ms |
504 KB |
Output is correct |
22 |
Correct |
4 ms |
504 KB |
Output is correct |
23 |
Correct |
3 ms |
504 KB |
Output is correct |
24 |
Correct |
3 ms |
504 KB |
Output is correct |
25 |
Correct |
8 ms |
1912 KB |
Output is correct |
26 |
Correct |
8 ms |
1916 KB |
Output is correct |
27 |
Correct |
9 ms |
1916 KB |
Output is correct |
28 |
Correct |
8 ms |
1400 KB |
Output is correct |
29 |
Correct |
11 ms |
1400 KB |
Output is correct |
30 |
Correct |
12 ms |
1528 KB |
Output is correct |
31 |
Correct |
12 ms |
1528 KB |
Output is correct |
32 |
Correct |
12 ms |
1528 KB |
Output is correct |
33 |
Correct |
79 ms |
15096 KB |
Output is correct |
34 |
Correct |
87 ms |
15008 KB |
Output is correct |
35 |
Correct |
97 ms |
15096 KB |
Output is correct |
36 |
Correct |
106 ms |
15096 KB |
Output is correct |
37 |
Correct |
94 ms |
17912 KB |
Output is correct |
38 |
Correct |
91 ms |
17784 KB |
Output is correct |
39 |
Correct |
95 ms |
17912 KB |
Output is correct |
40 |
Correct |
87 ms |
16888 KB |
Output is correct |
41 |
Correct |
60 ms |
12152 KB |
Output is correct |
42 |
Correct |
72 ms |
12152 KB |
Output is correct |
43 |
Correct |
132 ms |
12296 KB |
Output is correct |
44 |
Correct |
140 ms |
12280 KB |
Output is correct |
45 |
Correct |
66 ms |
7356 KB |
Output is correct |
46 |
Correct |
69 ms |
7416 KB |
Output is correct |
47 |
Correct |
126 ms |
12280 KB |
Output is correct |
48 |
Correct |
131 ms |
12328 KB |
Output is correct |
49 |
Correct |
2 ms |
376 KB |
Output is correct |
50 |
Correct |
2 ms |
256 KB |
Output is correct |
51 |
Correct |
2 ms |
376 KB |
Output is correct |
52 |
Correct |
2 ms |
380 KB |
Output is correct |
53 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
49736 KB |
Output is correct |
2 |
Correct |
33 ms |
36088 KB |
Output is correct |
3 |
Correct |
44 ms |
49620 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
46 ms |
49684 KB |
Output is correct |
6 |
Correct |
46 ms |
49656 KB |
Output is correct |
7 |
Correct |
46 ms |
49656 KB |
Output is correct |
8 |
Correct |
45 ms |
49664 KB |
Output is correct |
9 |
Correct |
47 ms |
49656 KB |
Output is correct |
10 |
Correct |
44 ms |
49680 KB |
Output is correct |
11 |
Correct |
44 ms |
49784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
412 ms |
77688 KB |
Output is correct |
3 |
Correct |
884 ms |
147420 KB |
Output is correct |
4 |
Correct |
898 ms |
148220 KB |
Output is correct |
5 |
Correct |
883 ms |
148216 KB |
Output is correct |
6 |
Correct |
287 ms |
86008 KB |
Output is correct |
7 |
Correct |
551 ms |
139256 KB |
Output is correct |
8 |
Correct |
598 ms |
148120 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
256 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
380 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
504 KB |
Output is correct |
10 |
Correct |
2 ms |
380 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
396 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
256 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
3 ms |
632 KB |
Output is correct |
18 |
Correct |
3 ms |
632 KB |
Output is correct |
19 |
Correct |
3 ms |
632 KB |
Output is correct |
20 |
Correct |
3 ms |
632 KB |
Output is correct |
21 |
Correct |
4 ms |
504 KB |
Output is correct |
22 |
Correct |
4 ms |
504 KB |
Output is correct |
23 |
Correct |
3 ms |
504 KB |
Output is correct |
24 |
Correct |
3 ms |
504 KB |
Output is correct |
25 |
Correct |
8 ms |
1912 KB |
Output is correct |
26 |
Correct |
8 ms |
1916 KB |
Output is correct |
27 |
Correct |
9 ms |
1916 KB |
Output is correct |
28 |
Correct |
8 ms |
1400 KB |
Output is correct |
29 |
Correct |
11 ms |
1400 KB |
Output is correct |
30 |
Correct |
12 ms |
1528 KB |
Output is correct |
31 |
Correct |
12 ms |
1528 KB |
Output is correct |
32 |
Correct |
12 ms |
1528 KB |
Output is correct |
33 |
Correct |
79 ms |
15096 KB |
Output is correct |
34 |
Correct |
87 ms |
15008 KB |
Output is correct |
35 |
Correct |
97 ms |
15096 KB |
Output is correct |
36 |
Correct |
106 ms |
15096 KB |
Output is correct |
37 |
Correct |
94 ms |
17912 KB |
Output is correct |
38 |
Correct |
91 ms |
17784 KB |
Output is correct |
39 |
Correct |
95 ms |
17912 KB |
Output is correct |
40 |
Correct |
87 ms |
16888 KB |
Output is correct |
41 |
Correct |
60 ms |
12152 KB |
Output is correct |
42 |
Correct |
72 ms |
12152 KB |
Output is correct |
43 |
Correct |
132 ms |
12296 KB |
Output is correct |
44 |
Correct |
140 ms |
12280 KB |
Output is correct |
45 |
Correct |
66 ms |
7356 KB |
Output is correct |
46 |
Correct |
69 ms |
7416 KB |
Output is correct |
47 |
Correct |
126 ms |
12280 KB |
Output is correct |
48 |
Correct |
131 ms |
12328 KB |
Output is correct |
49 |
Correct |
45 ms |
49736 KB |
Output is correct |
50 |
Correct |
33 ms |
36088 KB |
Output is correct |
51 |
Correct |
44 ms |
49620 KB |
Output is correct |
52 |
Correct |
2 ms |
256 KB |
Output is correct |
53 |
Correct |
46 ms |
49684 KB |
Output is correct |
54 |
Correct |
46 ms |
49656 KB |
Output is correct |
55 |
Correct |
46 ms |
49656 KB |
Output is correct |
56 |
Correct |
45 ms |
49664 KB |
Output is correct |
57 |
Correct |
47 ms |
49656 KB |
Output is correct |
58 |
Correct |
44 ms |
49680 KB |
Output is correct |
59 |
Correct |
44 ms |
49784 KB |
Output is correct |
60 |
Correct |
2 ms |
376 KB |
Output is correct |
61 |
Correct |
412 ms |
77688 KB |
Output is correct |
62 |
Correct |
884 ms |
147420 KB |
Output is correct |
63 |
Correct |
898 ms |
148220 KB |
Output is correct |
64 |
Correct |
883 ms |
148216 KB |
Output is correct |
65 |
Correct |
287 ms |
86008 KB |
Output is correct |
66 |
Correct |
551 ms |
139256 KB |
Output is correct |
67 |
Correct |
598 ms |
148120 KB |
Output is correct |
68 |
Correct |
1208 ms |
184012 KB |
Output is correct |
69 |
Correct |
1336 ms |
229004 KB |
Output is correct |
70 |
Correct |
1476 ms |
230260 KB |
Output is correct |
71 |
Correct |
1597 ms |
228960 KB |
Output is correct |
72 |
Correct |
1641 ms |
273304 KB |
Output is correct |
73 |
Correct |
1124 ms |
110980 KB |
Output is correct |
74 |
Correct |
1208 ms |
122948 KB |
Output is correct |
75 |
Correct |
1866 ms |
171224 KB |
Output is correct |
76 |
Correct |
1157 ms |
125964 KB |
Output is correct |
77 |
Correct |
1540 ms |
159304 KB |
Output is correct |
78 |
Correct |
2037 ms |
195168 KB |
Output is correct |
79 |
Correct |
1063 ms |
118776 KB |
Output is correct |
80 |
Correct |
1909 ms |
196528 KB |
Output is correct |
81 |
Correct |
1778 ms |
191096 KB |
Output is correct |
82 |
Correct |
929 ms |
168244 KB |
Output is correct |
83 |
Correct |
1644 ms |
273196 KB |
Output is correct |
84 |
Correct |
1612 ms |
273292 KB |
Output is correct |
85 |
Correct |
1548 ms |
273396 KB |
Output is correct |
86 |
Correct |
2 ms |
376 KB |
Output is correct |
87 |
Correct |
2 ms |
256 KB |
Output is correct |
88 |
Correct |
2 ms |
376 KB |
Output is correct |
89 |
Correct |
2 ms |
380 KB |
Output is correct |
90 |
Correct |
2 ms |
376 KB |
Output is correct |