# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
402430 |
2021-05-11T16:39:09 Z |
b00n0rp |
Rectangles (IOI19_rect) |
C++17 |
|
2696 ms |
399408 KB |
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define FORD(i,a,b) for(int i = a; i >= b; i --)
#define pii pair<int,int>
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
const ll MX = 2505;
ll ans = 0;
int n,m;
int gl[MX][MX],gr[MX][MX],gu[MX][MX],gd[MX][MX];
int glfuck[MX][MX],grfuck[MX][MX],gufuck[MX][MX],gdfuck[MX][MX];
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
void check_rectangle(int x1,int y1,int x2,int y2){
if(gr[x1][y1-1] == y2+1){
if(grfuck[x1][y1-1] < x2) return;
}
else if(gl[x1][y2+1] == y1-1){
if(glfuck[x1][y2+1] < x2) return;
}
else return;
if(gd[x1-1][y1] == x2+1){
if(gdfuck[x1-1][y1] < y2) return;
}
else if(gu[x2+1][y1] == x1-1){
if(gufuck[x2+1][y1] < y2) return;
}
else return;
ans++;
}
ll count_rectangles(vector<vi> a){
n = a.size();
m = a[0].size();
if(n <= 2 or m <= 2) return 0;
REP(i,n+2){
REP(j,m+2){
gl[i][j] = gr[i][j] = gu[i][j] = gd[i][j] = -1;
}
}
FORD(i,n-1,0){
stack<int> st;
REP(j,m){
while(st.size() and a[i][st.top()] <= a[i][j]){
if(j-1 > st.top()) gr[i][st.top()] = j;
st.pop();
}
st.push(j);
}
while(!st.empty()) st.pop();
FORD(j,m-1,0){
while(st.size() and a[i][st.top()] <= a[i][j]){
if(j+1 < st.top()) gl[i][st.top()] = j;
st.pop();
}
st.push(j);
}
REP(j,m){
if(gr[i][j] != -1){
if(gr[i][j] == gr[i+1][j]){
grfuck[i][j] = grfuck[i+1][j];
}
else if(gl[i+1][gr[i][j]] == j){
grfuck[i][j] = glfuck[i+1][gr[i][j]];
}
else grfuck[i][j] = i;
}
if(gl[i][j] != -1){
if(gl[i][j] == gl[i+1][j]){
glfuck[i][j] = glfuck[i+1][j];
}
else if(gr[i+1][gl[i][j]] == j){
glfuck[i][j] = grfuck[i+1][gl[i][j]];
}
else glfuck[i][j] = i;
}
}
}
FORD(j,m-1,0){
stack<int> st;
REP(i,n){
while(st.size() and a[st.top()][j] <= a[i][j]){
if(i-1 > st.top()) gd[st.top()][j] = i;
st.pop();
}
st.push(i);
}
while(!st.empty()) st.pop();
FORD(i,n-1,0){
while(st.size() and a[st.top()][j] <= a[i][j]){
if(i+1 < st.top()) gu[st.top()][j] = i;
st.pop();
}
st.push(i);
}
REP(i,n){
if(gd[i][j] != -1){
if(gd[i][j] == gd[i][j+1]){
gdfuck[i][j] = gdfuck[i][j+1];
}
else if(gu[gd[i][j]][j+1] == i){
gdfuck[i][j] = gufuck[gd[i][j]][j+1];
}
else gdfuck[i][j] = j;
}
if(gu[i][j] != -1){
if(gu[i][j] == gu[i][j+1]){
gufuck[i][j] = gufuck[i][j+1];
}
else if(gd[gu[i][j]][j+1] == i){
gufuck[i][j] = gdfuck[gu[i][j]][j+1];
}
else gufuck[i][j] = j;
}
}
}
vector<ll> bruh;
FOR(i,1,n-1){
FOR(j,1,m-1){
// topleft
if(gr[i][j-1] != -1 and gd[i-1][j] != -1){
bruh.pb((i)*MX*MX*MX+(j)*MX*MX+(gd[i-1][j]-1)*MX+gr[i][j-1]-1);
}
// topright
if(gl[i][j+1] != -1 and gd[i-1][j] != -1){
bruh.pb((i)*MX*MX*MX+(gl[i][j+1]+1)*MX*MX+(gd[i-1][j]-1)*MX+j);
}
// bottomleft
if(gr[i][j-1] != -1 and gu[i+1][j] != -1){
bruh.pb((gu[i+1][j]+1)*MX*MX*MX+(j)*MX*MX+(i)*MX+gr[i][j-1]-1);
}
// bottomright
if(gl[i][j+1] != -1 and gu[i+1][j] != -1){
bruh.pb((gu[i+1][j]+1)*MX*MX*MX+(gl[i][j+1]+1)*MX*MX+(i)*MX+j);
}
// clockwise
if(gr[i][j-1] != -1 and gd[i-1][gr[i][j-1]-1] != -1){
bruh.pb((i)*MX*MX*MX+(j)*MX*MX+(gd[i-1][gr[i][j-1]-1]-1)*MX+gr[i][j-1]-1);
}
// anti-clockwise
if(gl[i][j+1] != -1 and gd[i-1][gl[i][j+1]+1] != -1){
bruh.pb((i)*MX*MX*MX+(gl[i][j+1]+1)*MX*MX+(gd[i-1][gl[i][j+1]+1]-1)*MX+j);
}
}
}
sort(all(bruh));
REP(i,SZ(bruh)){
if(i == 0 or bruh[i] != bruh[i-1]){
check_rectangle(bruh[i]/(MX*MX*MX),(bruh[i]/(MX*MX))%MX,(bruh[i]/MX)%MX,bruh[i]%MX);
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
1228 KB |
Output is correct |
3 |
Correct |
2 ms |
1228 KB |
Output is correct |
4 |
Correct |
1 ms |
1228 KB |
Output is correct |
5 |
Correct |
1 ms |
844 KB |
Output is correct |
6 |
Correct |
1 ms |
1356 KB |
Output is correct |
7 |
Correct |
1 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
1356 KB |
Output is correct |
10 |
Correct |
1 ms |
1356 KB |
Output is correct |
11 |
Correct |
1 ms |
1356 KB |
Output is correct |
12 |
Correct |
1 ms |
1228 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
1228 KB |
Output is correct |
20 |
Correct |
1 ms |
844 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
1228 KB |
Output is correct |
3 |
Correct |
2 ms |
1228 KB |
Output is correct |
4 |
Correct |
1 ms |
1228 KB |
Output is correct |
5 |
Correct |
1 ms |
844 KB |
Output is correct |
6 |
Correct |
1 ms |
1356 KB |
Output is correct |
7 |
Correct |
1 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
1356 KB |
Output is correct |
10 |
Correct |
1 ms |
1356 KB |
Output is correct |
11 |
Correct |
1 ms |
1356 KB |
Output is correct |
12 |
Correct |
1 ms |
1228 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
1228 KB |
Output is correct |
20 |
Correct |
1 ms |
844 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
4 ms |
3020 KB |
Output is correct |
23 |
Correct |
3 ms |
3020 KB |
Output is correct |
24 |
Correct |
3 ms |
3020 KB |
Output is correct |
25 |
Correct |
3 ms |
3276 KB |
Output is correct |
26 |
Correct |
4 ms |
3276 KB |
Output is correct |
27 |
Correct |
5 ms |
3276 KB |
Output is correct |
28 |
Correct |
4 ms |
3276 KB |
Output is correct |
29 |
Correct |
3 ms |
3020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
1228 KB |
Output is correct |
3 |
Correct |
2 ms |
1228 KB |
Output is correct |
4 |
Correct |
1 ms |
1228 KB |
Output is correct |
5 |
Correct |
1 ms |
844 KB |
Output is correct |
6 |
Correct |
1 ms |
1356 KB |
Output is correct |
7 |
Correct |
1 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
1356 KB |
Output is correct |
10 |
Correct |
1 ms |
1356 KB |
Output is correct |
11 |
Correct |
1 ms |
1356 KB |
Output is correct |
12 |
Correct |
1 ms |
1228 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
4 ms |
3020 KB |
Output is correct |
18 |
Correct |
3 ms |
3020 KB |
Output is correct |
19 |
Correct |
3 ms |
3020 KB |
Output is correct |
20 |
Correct |
3 ms |
3276 KB |
Output is correct |
21 |
Correct |
4 ms |
3276 KB |
Output is correct |
22 |
Correct |
5 ms |
3276 KB |
Output is correct |
23 |
Correct |
4 ms |
3276 KB |
Output is correct |
24 |
Correct |
3 ms |
3020 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
1228 KB |
Output is correct |
28 |
Correct |
1 ms |
844 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
12 ms |
8388 KB |
Output is correct |
31 |
Correct |
11 ms |
8388 KB |
Output is correct |
32 |
Correct |
11 ms |
8388 KB |
Output is correct |
33 |
Correct |
12 ms |
8904 KB |
Output is correct |
34 |
Correct |
16 ms |
9412 KB |
Output is correct |
35 |
Correct |
20 ms |
9480 KB |
Output is correct |
36 |
Correct |
16 ms |
9412 KB |
Output is correct |
37 |
Correct |
16 ms |
9284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
1228 KB |
Output is correct |
3 |
Correct |
2 ms |
1228 KB |
Output is correct |
4 |
Correct |
1 ms |
1228 KB |
Output is correct |
5 |
Correct |
1 ms |
844 KB |
Output is correct |
6 |
Correct |
1 ms |
1356 KB |
Output is correct |
7 |
Correct |
1 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
1356 KB |
Output is correct |
10 |
Correct |
1 ms |
1356 KB |
Output is correct |
11 |
Correct |
1 ms |
1356 KB |
Output is correct |
12 |
Correct |
1 ms |
1228 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
4 ms |
3020 KB |
Output is correct |
18 |
Correct |
3 ms |
3020 KB |
Output is correct |
19 |
Correct |
3 ms |
3020 KB |
Output is correct |
20 |
Correct |
3 ms |
3276 KB |
Output is correct |
21 |
Correct |
4 ms |
3276 KB |
Output is correct |
22 |
Correct |
5 ms |
3276 KB |
Output is correct |
23 |
Correct |
4 ms |
3276 KB |
Output is correct |
24 |
Correct |
3 ms |
3020 KB |
Output is correct |
25 |
Correct |
12 ms |
8388 KB |
Output is correct |
26 |
Correct |
11 ms |
8388 KB |
Output is correct |
27 |
Correct |
11 ms |
8388 KB |
Output is correct |
28 |
Correct |
12 ms |
8904 KB |
Output is correct |
29 |
Correct |
16 ms |
9412 KB |
Output is correct |
30 |
Correct |
20 ms |
9480 KB |
Output is correct |
31 |
Correct |
16 ms |
9412 KB |
Output is correct |
32 |
Correct |
16 ms |
9284 KB |
Output is correct |
33 |
Correct |
1 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
204 KB |
Output is correct |
35 |
Correct |
1 ms |
1228 KB |
Output is correct |
36 |
Correct |
1 ms |
844 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
68 ms |
32868 KB |
Output is correct |
39 |
Correct |
70 ms |
32804 KB |
Output is correct |
40 |
Correct |
67 ms |
30600 KB |
Output is correct |
41 |
Correct |
59 ms |
30588 KB |
Output is correct |
42 |
Correct |
131 ms |
43740 KB |
Output is correct |
43 |
Correct |
138 ms |
43692 KB |
Output is correct |
44 |
Correct |
136 ms |
43780 KB |
Output is correct |
45 |
Correct |
120 ms |
41472 KB |
Output is correct |
46 |
Correct |
97 ms |
46212 KB |
Output is correct |
47 |
Correct |
128 ms |
50400 KB |
Output is correct |
48 |
Correct |
182 ms |
50384 KB |
Output is correct |
49 |
Correct |
186 ms |
50336 KB |
Output is correct |
50 |
Correct |
95 ms |
36596 KB |
Output is correct |
51 |
Correct |
101 ms |
25404 KB |
Output is correct |
52 |
Correct |
183 ms |
50224 KB |
Output is correct |
53 |
Correct |
172 ms |
50212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
588 KB |
Output is correct |
2 |
Correct |
3 ms |
588 KB |
Output is correct |
3 |
Correct |
2 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
2 ms |
588 KB |
Output is correct |
6 |
Correct |
2 ms |
588 KB |
Output is correct |
7 |
Correct |
2 ms |
588 KB |
Output is correct |
8 |
Correct |
2 ms |
588 KB |
Output is correct |
9 |
Correct |
3 ms |
580 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
1228 KB |
Output is correct |
4 |
Correct |
1 ms |
844 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
588 KB |
Output is correct |
7 |
Correct |
621 ms |
152524 KB |
Output is correct |
8 |
Correct |
1404 ms |
310244 KB |
Output is correct |
9 |
Correct |
1407 ms |
311324 KB |
Output is correct |
10 |
Correct |
1437 ms |
311336 KB |
Output is correct |
11 |
Correct |
289 ms |
73088 KB |
Output is correct |
12 |
Correct |
618 ms |
144468 KB |
Output is correct |
13 |
Correct |
636 ms |
147520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
1228 KB |
Output is correct |
3 |
Correct |
2 ms |
1228 KB |
Output is correct |
4 |
Correct |
1 ms |
1228 KB |
Output is correct |
5 |
Correct |
1 ms |
844 KB |
Output is correct |
6 |
Correct |
1 ms |
1356 KB |
Output is correct |
7 |
Correct |
1 ms |
1228 KB |
Output is correct |
8 |
Correct |
1 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
1356 KB |
Output is correct |
10 |
Correct |
1 ms |
1356 KB |
Output is correct |
11 |
Correct |
1 ms |
1356 KB |
Output is correct |
12 |
Correct |
1 ms |
1228 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
4 ms |
3020 KB |
Output is correct |
18 |
Correct |
3 ms |
3020 KB |
Output is correct |
19 |
Correct |
3 ms |
3020 KB |
Output is correct |
20 |
Correct |
3 ms |
3276 KB |
Output is correct |
21 |
Correct |
4 ms |
3276 KB |
Output is correct |
22 |
Correct |
5 ms |
3276 KB |
Output is correct |
23 |
Correct |
4 ms |
3276 KB |
Output is correct |
24 |
Correct |
3 ms |
3020 KB |
Output is correct |
25 |
Correct |
12 ms |
8388 KB |
Output is correct |
26 |
Correct |
11 ms |
8388 KB |
Output is correct |
27 |
Correct |
11 ms |
8388 KB |
Output is correct |
28 |
Correct |
12 ms |
8904 KB |
Output is correct |
29 |
Correct |
16 ms |
9412 KB |
Output is correct |
30 |
Correct |
20 ms |
9480 KB |
Output is correct |
31 |
Correct |
16 ms |
9412 KB |
Output is correct |
32 |
Correct |
16 ms |
9284 KB |
Output is correct |
33 |
Correct |
68 ms |
32868 KB |
Output is correct |
34 |
Correct |
70 ms |
32804 KB |
Output is correct |
35 |
Correct |
67 ms |
30600 KB |
Output is correct |
36 |
Correct |
59 ms |
30588 KB |
Output is correct |
37 |
Correct |
131 ms |
43740 KB |
Output is correct |
38 |
Correct |
138 ms |
43692 KB |
Output is correct |
39 |
Correct |
136 ms |
43780 KB |
Output is correct |
40 |
Correct |
120 ms |
41472 KB |
Output is correct |
41 |
Correct |
97 ms |
46212 KB |
Output is correct |
42 |
Correct |
128 ms |
50400 KB |
Output is correct |
43 |
Correct |
182 ms |
50384 KB |
Output is correct |
44 |
Correct |
186 ms |
50336 KB |
Output is correct |
45 |
Correct |
95 ms |
36596 KB |
Output is correct |
46 |
Correct |
101 ms |
25404 KB |
Output is correct |
47 |
Correct |
183 ms |
50224 KB |
Output is correct |
48 |
Correct |
172 ms |
50212 KB |
Output is correct |
49 |
Correct |
2 ms |
588 KB |
Output is correct |
50 |
Correct |
3 ms |
588 KB |
Output is correct |
51 |
Correct |
2 ms |
460 KB |
Output is correct |
52 |
Correct |
1 ms |
204 KB |
Output is correct |
53 |
Correct |
2 ms |
588 KB |
Output is correct |
54 |
Correct |
2 ms |
588 KB |
Output is correct |
55 |
Correct |
2 ms |
588 KB |
Output is correct |
56 |
Correct |
2 ms |
588 KB |
Output is correct |
57 |
Correct |
3 ms |
580 KB |
Output is correct |
58 |
Correct |
1 ms |
204 KB |
Output is correct |
59 |
Correct |
1 ms |
332 KB |
Output is correct |
60 |
Correct |
1 ms |
588 KB |
Output is correct |
61 |
Correct |
621 ms |
152524 KB |
Output is correct |
62 |
Correct |
1404 ms |
310244 KB |
Output is correct |
63 |
Correct |
1407 ms |
311324 KB |
Output is correct |
64 |
Correct |
1437 ms |
311336 KB |
Output is correct |
65 |
Correct |
289 ms |
73088 KB |
Output is correct |
66 |
Correct |
618 ms |
144468 KB |
Output is correct |
67 |
Correct |
636 ms |
147520 KB |
Output is correct |
68 |
Correct |
1 ms |
204 KB |
Output is correct |
69 |
Correct |
1 ms |
204 KB |
Output is correct |
70 |
Correct |
1 ms |
1228 KB |
Output is correct |
71 |
Correct |
1 ms |
844 KB |
Output is correct |
72 |
Correct |
1 ms |
204 KB |
Output is correct |
73 |
Correct |
1018 ms |
220924 KB |
Output is correct |
74 |
Correct |
1039 ms |
220924 KB |
Output is correct |
75 |
Correct |
872 ms |
187976 KB |
Output is correct |
76 |
Correct |
900 ms |
187936 KB |
Output is correct |
77 |
Correct |
2094 ms |
338020 KB |
Output is correct |
78 |
Correct |
1507 ms |
226872 KB |
Output is correct |
79 |
Correct |
1557 ms |
294544 KB |
Output is correct |
80 |
Correct |
2556 ms |
378224 KB |
Output is correct |
81 |
Correct |
1582 ms |
225652 KB |
Output is correct |
82 |
Correct |
2025 ms |
383800 KB |
Output is correct |
83 |
Correct |
2696 ms |
397596 KB |
Output is correct |
84 |
Correct |
1426 ms |
234804 KB |
Output is correct |
85 |
Correct |
2497 ms |
399408 KB |
Output is correct |
86 |
Correct |
2498 ms |
392196 KB |
Output is correct |
87 |
Correct |
1164 ms |
265248 KB |
Output is correct |
88 |
Correct |
2092 ms |
358404 KB |
Output is correct |
89 |
Correct |
2072 ms |
358348 KB |
Output is correct |
90 |
Correct |
2209 ms |
358376 KB |
Output is correct |