# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
146023 |
2019-08-21T15:22:29 Z |
jwvg0425 |
Rectangles (IOI19_rect) |
C++17 |
|
4652 ms |
784632 KB |
#include "rect.h"
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <stack>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
#define MAXL 2505
using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
class FenwickTree
{
public:
FenwickTree(int k)
{
data.resize(k);
}
i64 sum(int n)
{
i64 ans = 0;
while (n > 0)
{
ans += data[n];
n -= (n & -n);
}
return ans;
}
void add(int n, i64 num)
{
while (n < data.size())
{
data[n] += num;
n += (n & -n);
}
}
private:
vector<i64> data;
};
// (구간 길이, 반대편 확장 가능 길이)
vector<ii> rseg[MAXL][MAXL];
vector<ii> dseg[MAXL][MAXL];
long long count_rectangles(vector<vector<int>> a)
{
i64 ans = 0;
int n = a.size();
int m = a[0].size();
for (int x = 0; x < n; x++)
{
stack<int> s;
for (int y = 0; y < m; y++)
{
while (!s.empty() && a[x][s.top()] <= a[x][y])
{
int l = y - s.top() - 1;
if (l > 0)
rseg[x][s.top()].emplace_back(l, 1);
s.pop();
}
s.push(y);
}
stack<int> s2;
for (int y = m - 1; y >= 0; y--)
{
while (!s2.empty() && a[x][s2.top()] <= a[x][y])
{
int l = s2.top() - y - 1;
if (a[x][s2.top()] != a[x][y] && l > 0)
rseg[x][y].emplace_back(l, 1);
s2.pop();
}
s2.push(y);
}
}
for (int y = 0; y < m; y++)
{
stack<int> s;
for (int x = 0; x < n; x++)
{
while (!s.empty() && a[s.top()][y] <= a[x][y])
{
int l = x - s.top() - 1;
if (l > 0)
dseg[s.top()][y].emplace_back(l, 1);
s.pop();
}
s.push(x);
}
stack<int> s2;
for (int x = n - 1; x >= 0; x--)
{
while (!s2.empty() && a[s2.top()][y] <= a[x][y])
{
int l = s2.top() - x - 1;
if (a[s2.top()][y] != a[x][y] && l > 0)
dseg[x][y].emplace_back(l, 1);
s2.pop();
}
s2.push(x);
}
}
for (int x = 0; x < n; x++)
{
for (int y = 0; y < m; y++)
{
sort(all(rseg[x][y]));
sort(all(dseg[x][y]));
}
}
for (int y = 0; y < m; y++)
{
for (int x = n - 2; x >= 0; x--)
{
for (auto& rv : rseg[x][y])
{
auto iter = lower_bound(all(rseg[x + 1][y]), rv);
if (iter != rseg[x + 1][y].end() && iter->xx == rv.xx)
rv.yy = iter->yy + 1;
}
}
}
for (int x = 0; x < n; x++)
{
for (int y = m - 2; y >= 0; y--)
{
for (auto& dv : dseg[x][y])
{
auto iter = lower_bound(all(dseg[x][y + 1]), dv);
if (iter != dseg[x][y + 1].end() && iter->xx == dv.xx)
dv.yy = iter->yy + 1;
}
}
}
for (int x = 0; x < n; x++)
{
for (int y = 0; y < m; y++)
{
sort(all(rseg[x][y]), [](const ii& l, const ii& r) { return l.yy < r.yy; });
sort(all(dseg[x][y]));
}
}
FenwickTree tree(2505);
for (int x = 1; x < n - 1; x++)
{
for (int y = 1; y < m - 1; y++)
{
int didx = 0;
for (auto& ri : rseg[x][y - 1])
{
while (didx < dseg[x - 1][y].size() && dseg[x - 1][y][didx].xx <= ri.yy)
{
tree.add(dseg[x - 1][y][didx].yy, 1);
didx++;
}
ans += tree.sum(2503) - tree.sum(ri.xx - 1);
}
for (int dx = 0; dx < didx; dx++)
tree.add(dseg[x - 1][y][dx].yy, -1);
}
}
return ans;
}
Compilation message
rect.cpp: In member function 'void FenwickTree::add(int, i64)':
rect.cpp:53:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (n < data.size())
~~^~~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:197:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (didx < dseg[x - 1][y].size() && dseg[x - 1][y][didx].xx <= ri.yy)
~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
265 ms |
295160 KB |
Output is correct |
2 |
Correct |
267 ms |
295264 KB |
Output is correct |
3 |
Correct |
266 ms |
295032 KB |
Output is correct |
4 |
Correct |
275 ms |
295100 KB |
Output is correct |
5 |
Correct |
265 ms |
295000 KB |
Output is correct |
6 |
Correct |
273 ms |
295052 KB |
Output is correct |
7 |
Correct |
267 ms |
295260 KB |
Output is correct |
8 |
Correct |
267 ms |
295052 KB |
Output is correct |
9 |
Correct |
265 ms |
295032 KB |
Output is correct |
10 |
Correct |
267 ms |
295168 KB |
Output is correct |
11 |
Correct |
265 ms |
295032 KB |
Output is correct |
12 |
Correct |
266 ms |
295036 KB |
Output is correct |
13 |
Correct |
267 ms |
295136 KB |
Output is correct |
14 |
Correct |
268 ms |
295032 KB |
Output is correct |
15 |
Correct |
267 ms |
295032 KB |
Output is correct |
16 |
Correct |
274 ms |
295132 KB |
Output is correct |
17 |
Correct |
270 ms |
295080 KB |
Output is correct |
18 |
Correct |
267 ms |
295016 KB |
Output is correct |
19 |
Correct |
266 ms |
295160 KB |
Output is correct |
20 |
Correct |
265 ms |
295032 KB |
Output is correct |
21 |
Correct |
267 ms |
295108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
265 ms |
295160 KB |
Output is correct |
2 |
Correct |
267 ms |
295264 KB |
Output is correct |
3 |
Correct |
266 ms |
295032 KB |
Output is correct |
4 |
Correct |
275 ms |
295100 KB |
Output is correct |
5 |
Correct |
265 ms |
295000 KB |
Output is correct |
6 |
Correct |
273 ms |
295052 KB |
Output is correct |
7 |
Correct |
267 ms |
295260 KB |
Output is correct |
8 |
Correct |
267 ms |
295052 KB |
Output is correct |
9 |
Correct |
265 ms |
295032 KB |
Output is correct |
10 |
Correct |
267 ms |
295168 KB |
Output is correct |
11 |
Correct |
265 ms |
295032 KB |
Output is correct |
12 |
Correct |
266 ms |
295036 KB |
Output is correct |
13 |
Correct |
267 ms |
295136 KB |
Output is correct |
14 |
Correct |
268 ms |
295032 KB |
Output is correct |
15 |
Correct |
267 ms |
295032 KB |
Output is correct |
16 |
Correct |
274 ms |
295132 KB |
Output is correct |
17 |
Correct |
270 ms |
295560 KB |
Output is correct |
18 |
Correct |
269 ms |
295532 KB |
Output is correct |
19 |
Correct |
267 ms |
295672 KB |
Output is correct |
20 |
Correct |
266 ms |
295160 KB |
Output is correct |
21 |
Correct |
270 ms |
295416 KB |
Output is correct |
22 |
Correct |
271 ms |
295360 KB |
Output is correct |
23 |
Correct |
267 ms |
295260 KB |
Output is correct |
24 |
Correct |
266 ms |
295176 KB |
Output is correct |
25 |
Correct |
270 ms |
295080 KB |
Output is correct |
26 |
Correct |
267 ms |
295016 KB |
Output is correct |
27 |
Correct |
266 ms |
295160 KB |
Output is correct |
28 |
Correct |
265 ms |
295032 KB |
Output is correct |
29 |
Correct |
267 ms |
295108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
265 ms |
295160 KB |
Output is correct |
2 |
Correct |
267 ms |
295264 KB |
Output is correct |
3 |
Correct |
266 ms |
295032 KB |
Output is correct |
4 |
Correct |
275 ms |
295100 KB |
Output is correct |
5 |
Correct |
265 ms |
295000 KB |
Output is correct |
6 |
Correct |
273 ms |
295052 KB |
Output is correct |
7 |
Correct |
267 ms |
295260 KB |
Output is correct |
8 |
Correct |
267 ms |
295052 KB |
Output is correct |
9 |
Correct |
265 ms |
295032 KB |
Output is correct |
10 |
Correct |
267 ms |
295168 KB |
Output is correct |
11 |
Correct |
265 ms |
295032 KB |
Output is correct |
12 |
Correct |
266 ms |
295036 KB |
Output is correct |
13 |
Correct |
267 ms |
295136 KB |
Output is correct |
14 |
Correct |
268 ms |
295032 KB |
Output is correct |
15 |
Correct |
267 ms |
295032 KB |
Output is correct |
16 |
Correct |
274 ms |
295132 KB |
Output is correct |
17 |
Correct |
270 ms |
295560 KB |
Output is correct |
18 |
Correct |
269 ms |
295532 KB |
Output is correct |
19 |
Correct |
267 ms |
295672 KB |
Output is correct |
20 |
Correct |
266 ms |
295160 KB |
Output is correct |
21 |
Correct |
270 ms |
295416 KB |
Output is correct |
22 |
Correct |
271 ms |
295360 KB |
Output is correct |
23 |
Correct |
267 ms |
295260 KB |
Output is correct |
24 |
Correct |
266 ms |
295176 KB |
Output is correct |
25 |
Correct |
278 ms |
297896 KB |
Output is correct |
26 |
Correct |
277 ms |
297980 KB |
Output is correct |
27 |
Correct |
281 ms |
297944 KB |
Output is correct |
28 |
Correct |
281 ms |
296312 KB |
Output is correct |
29 |
Correct |
282 ms |
296824 KB |
Output is correct |
30 |
Correct |
281 ms |
296920 KB |
Output is correct |
31 |
Correct |
282 ms |
296696 KB |
Output is correct |
32 |
Correct |
285 ms |
296696 KB |
Output is correct |
33 |
Correct |
270 ms |
295080 KB |
Output is correct |
34 |
Correct |
267 ms |
295016 KB |
Output is correct |
35 |
Correct |
266 ms |
295160 KB |
Output is correct |
36 |
Correct |
265 ms |
295032 KB |
Output is correct |
37 |
Correct |
267 ms |
295108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
265 ms |
295160 KB |
Output is correct |
2 |
Correct |
267 ms |
295264 KB |
Output is correct |
3 |
Correct |
266 ms |
295032 KB |
Output is correct |
4 |
Correct |
275 ms |
295100 KB |
Output is correct |
5 |
Correct |
265 ms |
295000 KB |
Output is correct |
6 |
Correct |
273 ms |
295052 KB |
Output is correct |
7 |
Correct |
267 ms |
295260 KB |
Output is correct |
8 |
Correct |
267 ms |
295052 KB |
Output is correct |
9 |
Correct |
265 ms |
295032 KB |
Output is correct |
10 |
Correct |
267 ms |
295168 KB |
Output is correct |
11 |
Correct |
265 ms |
295032 KB |
Output is correct |
12 |
Correct |
266 ms |
295036 KB |
Output is correct |
13 |
Correct |
267 ms |
295136 KB |
Output is correct |
14 |
Correct |
268 ms |
295032 KB |
Output is correct |
15 |
Correct |
267 ms |
295032 KB |
Output is correct |
16 |
Correct |
274 ms |
295132 KB |
Output is correct |
17 |
Correct |
270 ms |
295560 KB |
Output is correct |
18 |
Correct |
269 ms |
295532 KB |
Output is correct |
19 |
Correct |
267 ms |
295672 KB |
Output is correct |
20 |
Correct |
266 ms |
295160 KB |
Output is correct |
21 |
Correct |
270 ms |
295416 KB |
Output is correct |
22 |
Correct |
271 ms |
295360 KB |
Output is correct |
23 |
Correct |
267 ms |
295260 KB |
Output is correct |
24 |
Correct |
266 ms |
295176 KB |
Output is correct |
25 |
Correct |
278 ms |
297896 KB |
Output is correct |
26 |
Correct |
277 ms |
297980 KB |
Output is correct |
27 |
Correct |
281 ms |
297944 KB |
Output is correct |
28 |
Correct |
281 ms |
296312 KB |
Output is correct |
29 |
Correct |
282 ms |
296824 KB |
Output is correct |
30 |
Correct |
281 ms |
296920 KB |
Output is correct |
31 |
Correct |
282 ms |
296696 KB |
Output is correct |
32 |
Correct |
285 ms |
296696 KB |
Output is correct |
33 |
Correct |
375 ms |
314352 KB |
Output is correct |
34 |
Correct |
375 ms |
309624 KB |
Output is correct |
35 |
Correct |
348 ms |
309624 KB |
Output is correct |
36 |
Correct |
349 ms |
304664 KB |
Output is correct |
37 |
Correct |
507 ms |
329656 KB |
Output is correct |
38 |
Correct |
522 ms |
329592 KB |
Output is correct |
39 |
Correct |
505 ms |
329620 KB |
Output is correct |
40 |
Correct |
496 ms |
327388 KB |
Output is correct |
41 |
Correct |
378 ms |
306612 KB |
Output is correct |
42 |
Correct |
412 ms |
309276 KB |
Output is correct |
43 |
Correct |
538 ms |
316920 KB |
Output is correct |
44 |
Correct |
529 ms |
317232 KB |
Output is correct |
45 |
Correct |
387 ms |
306040 KB |
Output is correct |
46 |
Correct |
390 ms |
306124 KB |
Output is correct |
47 |
Correct |
505 ms |
315512 KB |
Output is correct |
48 |
Correct |
515 ms |
315684 KB |
Output is correct |
49 |
Correct |
270 ms |
295080 KB |
Output is correct |
50 |
Correct |
267 ms |
295016 KB |
Output is correct |
51 |
Correct |
266 ms |
295160 KB |
Output is correct |
52 |
Correct |
265 ms |
295032 KB |
Output is correct |
53 |
Correct |
267 ms |
295108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
269 ms |
295416 KB |
Output is correct |
2 |
Correct |
269 ms |
295384 KB |
Output is correct |
3 |
Correct |
271 ms |
295032 KB |
Output is correct |
4 |
Correct |
265 ms |
295004 KB |
Output is correct |
5 |
Correct |
269 ms |
295416 KB |
Output is correct |
6 |
Correct |
269 ms |
295288 KB |
Output is correct |
7 |
Correct |
267 ms |
295288 KB |
Output is correct |
8 |
Correct |
267 ms |
295288 KB |
Output is correct |
9 |
Correct |
267 ms |
295288 KB |
Output is correct |
10 |
Correct |
266 ms |
295160 KB |
Output is correct |
11 |
Correct |
265 ms |
295288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
263 ms |
295084 KB |
Output is correct |
2 |
Correct |
975 ms |
362416 KB |
Output is correct |
3 |
Correct |
1931 ms |
441188 KB |
Output is correct |
4 |
Correct |
1994 ms |
442040 KB |
Output is correct |
5 |
Correct |
1930 ms |
441984 KB |
Output is correct |
6 |
Correct |
471 ms |
319368 KB |
Output is correct |
7 |
Correct |
742 ms |
341112 KB |
Output is correct |
8 |
Correct |
772 ms |
344312 KB |
Output is correct |
9 |
Correct |
270 ms |
295080 KB |
Output is correct |
10 |
Correct |
267 ms |
295016 KB |
Output is correct |
11 |
Correct |
266 ms |
295160 KB |
Output is correct |
12 |
Correct |
265 ms |
295032 KB |
Output is correct |
13 |
Correct |
267 ms |
295108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
265 ms |
295160 KB |
Output is correct |
2 |
Correct |
267 ms |
295264 KB |
Output is correct |
3 |
Correct |
266 ms |
295032 KB |
Output is correct |
4 |
Correct |
275 ms |
295100 KB |
Output is correct |
5 |
Correct |
265 ms |
295000 KB |
Output is correct |
6 |
Correct |
273 ms |
295052 KB |
Output is correct |
7 |
Correct |
267 ms |
295260 KB |
Output is correct |
8 |
Correct |
267 ms |
295052 KB |
Output is correct |
9 |
Correct |
265 ms |
295032 KB |
Output is correct |
10 |
Correct |
267 ms |
295168 KB |
Output is correct |
11 |
Correct |
265 ms |
295032 KB |
Output is correct |
12 |
Correct |
266 ms |
295036 KB |
Output is correct |
13 |
Correct |
267 ms |
295136 KB |
Output is correct |
14 |
Correct |
268 ms |
295032 KB |
Output is correct |
15 |
Correct |
267 ms |
295032 KB |
Output is correct |
16 |
Correct |
274 ms |
295132 KB |
Output is correct |
17 |
Correct |
270 ms |
295560 KB |
Output is correct |
18 |
Correct |
269 ms |
295532 KB |
Output is correct |
19 |
Correct |
267 ms |
295672 KB |
Output is correct |
20 |
Correct |
266 ms |
295160 KB |
Output is correct |
21 |
Correct |
270 ms |
295416 KB |
Output is correct |
22 |
Correct |
271 ms |
295360 KB |
Output is correct |
23 |
Correct |
267 ms |
295260 KB |
Output is correct |
24 |
Correct |
266 ms |
295176 KB |
Output is correct |
25 |
Correct |
278 ms |
297896 KB |
Output is correct |
26 |
Correct |
277 ms |
297980 KB |
Output is correct |
27 |
Correct |
281 ms |
297944 KB |
Output is correct |
28 |
Correct |
281 ms |
296312 KB |
Output is correct |
29 |
Correct |
282 ms |
296824 KB |
Output is correct |
30 |
Correct |
281 ms |
296920 KB |
Output is correct |
31 |
Correct |
282 ms |
296696 KB |
Output is correct |
32 |
Correct |
285 ms |
296696 KB |
Output is correct |
33 |
Correct |
375 ms |
314352 KB |
Output is correct |
34 |
Correct |
375 ms |
309624 KB |
Output is correct |
35 |
Correct |
348 ms |
309624 KB |
Output is correct |
36 |
Correct |
349 ms |
304664 KB |
Output is correct |
37 |
Correct |
507 ms |
329656 KB |
Output is correct |
38 |
Correct |
522 ms |
329592 KB |
Output is correct |
39 |
Correct |
505 ms |
329620 KB |
Output is correct |
40 |
Correct |
496 ms |
327388 KB |
Output is correct |
41 |
Correct |
378 ms |
306612 KB |
Output is correct |
42 |
Correct |
412 ms |
309276 KB |
Output is correct |
43 |
Correct |
538 ms |
316920 KB |
Output is correct |
44 |
Correct |
529 ms |
317232 KB |
Output is correct |
45 |
Correct |
387 ms |
306040 KB |
Output is correct |
46 |
Correct |
390 ms |
306124 KB |
Output is correct |
47 |
Correct |
505 ms |
315512 KB |
Output is correct |
48 |
Correct |
515 ms |
315684 KB |
Output is correct |
49 |
Correct |
269 ms |
295416 KB |
Output is correct |
50 |
Correct |
269 ms |
295384 KB |
Output is correct |
51 |
Correct |
271 ms |
295032 KB |
Output is correct |
52 |
Correct |
265 ms |
295004 KB |
Output is correct |
53 |
Correct |
269 ms |
295416 KB |
Output is correct |
54 |
Correct |
269 ms |
295288 KB |
Output is correct |
55 |
Correct |
267 ms |
295288 KB |
Output is correct |
56 |
Correct |
267 ms |
295288 KB |
Output is correct |
57 |
Correct |
267 ms |
295288 KB |
Output is correct |
58 |
Correct |
266 ms |
295160 KB |
Output is correct |
59 |
Correct |
265 ms |
295288 KB |
Output is correct |
60 |
Correct |
263 ms |
295084 KB |
Output is correct |
61 |
Correct |
975 ms |
362416 KB |
Output is correct |
62 |
Correct |
1931 ms |
441188 KB |
Output is correct |
63 |
Correct |
1994 ms |
442040 KB |
Output is correct |
64 |
Correct |
1930 ms |
441984 KB |
Output is correct |
65 |
Correct |
471 ms |
319368 KB |
Output is correct |
66 |
Correct |
742 ms |
341112 KB |
Output is correct |
67 |
Correct |
772 ms |
344312 KB |
Output is correct |
68 |
Correct |
1957 ms |
569176 KB |
Output is correct |
69 |
Correct |
2012 ms |
473148 KB |
Output is correct |
70 |
Correct |
1483 ms |
473108 KB |
Output is correct |
71 |
Correct |
1289 ms |
405976 KB |
Output is correct |
72 |
Correct |
4632 ms |
784632 KB |
Output is correct |
73 |
Correct |
2490 ms |
476816 KB |
Output is correct |
74 |
Correct |
2634 ms |
495352 KB |
Output is correct |
75 |
Correct |
4048 ms |
598380 KB |
Output is correct |
76 |
Correct |
2516 ms |
493176 KB |
Output is correct |
77 |
Correct |
3446 ms |
559444 KB |
Output is correct |
78 |
Correct |
4133 ms |
625492 KB |
Output is correct |
79 |
Correct |
2358 ms |
475220 KB |
Output is correct |
80 |
Correct |
4050 ms |
609296 KB |
Output is correct |
81 |
Correct |
3884 ms |
599800 KB |
Output is correct |
82 |
Correct |
2794 ms |
588972 KB |
Output is correct |
83 |
Correct |
4652 ms |
784376 KB |
Output is correct |
84 |
Correct |
4588 ms |
784548 KB |
Output is correct |
85 |
Correct |
4600 ms |
784520 KB |
Output is correct |
86 |
Correct |
270 ms |
295080 KB |
Output is correct |
87 |
Correct |
267 ms |
295016 KB |
Output is correct |
88 |
Correct |
266 ms |
295160 KB |
Output is correct |
89 |
Correct |
265 ms |
295032 KB |
Output is correct |
90 |
Correct |
267 ms |
295108 KB |
Output is correct |