# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
402213 |
2021-05-11T12:31:21 Z |
okokok |
Rectangles (IOI19_rect) |
C++14 |
|
5000 ms |
904448 KB |
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#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];
pii rows[MX][MX],cols[MX][MX];
vector<pair<ll,int> > row_map,col_map;
bitset<MX*MX*6> b1,b2;
vector<pair<ll,pii> > quer_row,quer_col;
void check_rectangle(int x1,int y1,int x2,int y2,int q){
quer_row.pb({(y1-1)*MX*MX+(y2+1)*MX+x1,{x2,q}});
quer_col.pb({(x1-1)*MX*MX+(x2+1)*MX+y1,{y2,q}});
// cout << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
// cout << (y1-1)*MX*MX+(y2+1)*MX+x1 << " " << x2 << "\n";
// cout << (x1-1)*MX*MX+(x2+1)*MX+y1 << " " << y2 << "\n";
}
ll count_rectangles(vector<vi> a){
n = a.size();
m = a[0].size();
if(n <= 2 or m <= 2) return 0;
FORD(i,n-1,0){
stack<int> st;
REP(j,m){
gl[i][j] = gr[i][j] = gu[i][j] = gd[i][j] = -1;
}
REP(j,m){
while(st.size() and a[i][st.top()] <= a[i][j]){
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]){
gl[i][st.top()] = j;
st.pop();
}
st.push(j);
}
REP(j,m){
if(gr[i][j] != -1 and gr[i][j] != j+1){
ll val = j*MX*MX+gr[i][j]*MX+i;
if(rows[j][gr[i][j]].F == i+1){
rows[j][gr[i][j]].F--;
}
else{
rows[j][gr[i][j]] = {i,i};
}
row_map.pb({val,rows[j][gr[i][j]].S});
}
if(gl[i][j] != -1 and gl[i][j] != j-1 and gr[i][gl[i][j]] != j){
ll val = gl[i][j]*MX*MX+j*MX+i;
if(rows[gl[i][j]][j].F == i+1){
rows[gl[i][j]][j].F--;
}
else{
rows[gl[i][j]][j] = {i,i};
}
row_map.pb({val,rows[gl[i][j]][j].S});
}
}
}
FORD(j,m-1,0){
stack<int> st;
REP(i,n){
while(st.size() and a[st.top()][j] <= a[i][j]){
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]){
gu[st.top()][j] = i;
st.pop();
}
st.push(i);
}
REP(i,n){
if(gd[i][j] != -1 and gd[i][j] != i+1){
ll val = i*MX*MX+gd[i][j]*MX+j;
if(cols[i][gd[i][j]].F == j+1){
cols[i][gd[i][j]].F--;
}
else{
cols[i][gd[i][j]] = {j,j};
}
col_map.pb({val,cols[i][gd[i][j]].S});
}
if(gu[i][j] != -1 and gu[i][j] != i-1 and gd[gu[i][j]][j] != i){
ll val = gu[i][j]*MX*MX+i*MX+j;
if(cols[gu[i][j]][i].F == j+1){
cols[gu[i][j]][i].F--;
}
else{
cols[gu[i][j]][i] = {j,j};
}
col_map.pb({val,cols[gu[i][j]][i].S});
}
}
}
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));
int q = 0;
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,q);
q++;
}
}
sort(all(quer_col));
sort(all(quer_row));
sort(all(col_map));
sort(all(row_map));
int cur = 0;
for(auto x:col_map){
// cout << "col: " << x.F << " " << x.S << "\n";
while(cur < q and quer_col[cur].F < x.F) cur++;
while(cur < q and quer_col[cur].F == x.F){
if(quer_col[cur].S.F <= x.S) b1[quer_col[cur].S.S] = 1;
cur++;
}
}
cur = 0;
for(auto x:row_map){
// cout << "row: " << x.F << " " << x.S << "\n";
while(cur < q and quer_row[cur].F < x.F) cur++;
while(cur < q and quer_row[cur].F == x.F){
if(quer_row[cur].S.F <= x.S) b2[quer_row[cur].S.S] = 1;
cur++;
}
}
REP(i,q){
if(b1[i] and b2[i]) ans++;
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
3 ms |
1356 KB |
Output is correct |
3 |
Correct |
2 ms |
1356 KB |
Output is correct |
4 |
Correct |
3 ms |
1356 KB |
Output is correct |
5 |
Correct |
2 ms |
844 KB |
Output is correct |
6 |
Correct |
3 ms |
1356 KB |
Output is correct |
7 |
Correct |
2 ms |
1100 KB |
Output is correct |
8 |
Correct |
1 ms |
684 KB |
Output is correct |
9 |
Correct |
3 ms |
1324 KB |
Output is correct |
10 |
Correct |
2 ms |
1228 KB |
Output is correct |
11 |
Correct |
3 ms |
1228 KB |
Output is correct |
12 |
Correct |
2 ms |
1228 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
304 KB |
Output is correct |
15 |
Correct |
1 ms |
428 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 |
2 ms |
1100 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 |
3 ms |
1356 KB |
Output is correct |
3 |
Correct |
2 ms |
1356 KB |
Output is correct |
4 |
Correct |
3 ms |
1356 KB |
Output is correct |
5 |
Correct |
2 ms |
844 KB |
Output is correct |
6 |
Correct |
3 ms |
1356 KB |
Output is correct |
7 |
Correct |
2 ms |
1100 KB |
Output is correct |
8 |
Correct |
1 ms |
684 KB |
Output is correct |
9 |
Correct |
3 ms |
1324 KB |
Output is correct |
10 |
Correct |
2 ms |
1228 KB |
Output is correct |
11 |
Correct |
3 ms |
1228 KB |
Output is correct |
12 |
Correct |
2 ms |
1228 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
304 KB |
Output is correct |
15 |
Correct |
1 ms |
428 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 |
2 ms |
1100 KB |
Output is correct |
20 |
Correct |
1 ms |
844 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
11 ms |
4164 KB |
Output is correct |
23 |
Correct |
11 ms |
4168 KB |
Output is correct |
24 |
Correct |
12 ms |
4156 KB |
Output is correct |
25 |
Correct |
10 ms |
3524 KB |
Output is correct |
26 |
Correct |
13 ms |
4036 KB |
Output is correct |
27 |
Correct |
13 ms |
3948 KB |
Output is correct |
28 |
Correct |
14 ms |
4160 KB |
Output is correct |
29 |
Correct |
6 ms |
2892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
3 ms |
1356 KB |
Output is correct |
3 |
Correct |
2 ms |
1356 KB |
Output is correct |
4 |
Correct |
3 ms |
1356 KB |
Output is correct |
5 |
Correct |
2 ms |
844 KB |
Output is correct |
6 |
Correct |
3 ms |
1356 KB |
Output is correct |
7 |
Correct |
2 ms |
1100 KB |
Output is correct |
8 |
Correct |
1 ms |
684 KB |
Output is correct |
9 |
Correct |
3 ms |
1324 KB |
Output is correct |
10 |
Correct |
2 ms |
1228 KB |
Output is correct |
11 |
Correct |
3 ms |
1228 KB |
Output is correct |
12 |
Correct |
2 ms |
1228 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
304 KB |
Output is correct |
15 |
Correct |
1 ms |
428 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
11 ms |
4164 KB |
Output is correct |
18 |
Correct |
11 ms |
4168 KB |
Output is correct |
19 |
Correct |
12 ms |
4156 KB |
Output is correct |
20 |
Correct |
10 ms |
3524 KB |
Output is correct |
21 |
Correct |
13 ms |
4036 KB |
Output is correct |
22 |
Correct |
13 ms |
3948 KB |
Output is correct |
23 |
Correct |
14 ms |
4160 KB |
Output is correct |
24 |
Correct |
6 ms |
2892 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
2 ms |
1100 KB |
Output is correct |
28 |
Correct |
1 ms |
844 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
69 ms |
17708 KB |
Output is correct |
31 |
Correct |
71 ms |
17900 KB |
Output is correct |
32 |
Correct |
77 ms |
17932 KB |
Output is correct |
33 |
Correct |
63 ms |
13500 KB |
Output is correct |
34 |
Correct |
92 ms |
18268 KB |
Output is correct |
35 |
Correct |
92 ms |
18524 KB |
Output is correct |
36 |
Correct |
88 ms |
17824 KB |
Output is correct |
37 |
Correct |
85 ms |
17716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
3 ms |
1356 KB |
Output is correct |
3 |
Correct |
2 ms |
1356 KB |
Output is correct |
4 |
Correct |
3 ms |
1356 KB |
Output is correct |
5 |
Correct |
2 ms |
844 KB |
Output is correct |
6 |
Correct |
3 ms |
1356 KB |
Output is correct |
7 |
Correct |
2 ms |
1100 KB |
Output is correct |
8 |
Correct |
1 ms |
684 KB |
Output is correct |
9 |
Correct |
3 ms |
1324 KB |
Output is correct |
10 |
Correct |
2 ms |
1228 KB |
Output is correct |
11 |
Correct |
3 ms |
1228 KB |
Output is correct |
12 |
Correct |
2 ms |
1228 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
304 KB |
Output is correct |
15 |
Correct |
1 ms |
428 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
11 ms |
4164 KB |
Output is correct |
18 |
Correct |
11 ms |
4168 KB |
Output is correct |
19 |
Correct |
12 ms |
4156 KB |
Output is correct |
20 |
Correct |
10 ms |
3524 KB |
Output is correct |
21 |
Correct |
13 ms |
4036 KB |
Output is correct |
22 |
Correct |
13 ms |
3948 KB |
Output is correct |
23 |
Correct |
14 ms |
4160 KB |
Output is correct |
24 |
Correct |
6 ms |
2892 KB |
Output is correct |
25 |
Correct |
69 ms |
17708 KB |
Output is correct |
26 |
Correct |
71 ms |
17900 KB |
Output is correct |
27 |
Correct |
77 ms |
17932 KB |
Output is correct |
28 |
Correct |
63 ms |
13500 KB |
Output is correct |
29 |
Correct |
92 ms |
18268 KB |
Output is correct |
30 |
Correct |
92 ms |
18524 KB |
Output is correct |
31 |
Correct |
88 ms |
17824 KB |
Output is correct |
32 |
Correct |
85 ms |
17716 KB |
Output is correct |
33 |
Correct |
1 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
204 KB |
Output is correct |
35 |
Correct |
2 ms |
1100 KB |
Output is correct |
36 |
Correct |
1 ms |
844 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Correct |
691 ms |
105124 KB |
Output is correct |
39 |
Correct |
645 ms |
105092 KB |
Output is correct |
40 |
Correct |
470 ms |
90284 KB |
Output is correct |
41 |
Correct |
462 ms |
90236 KB |
Output is correct |
42 |
Correct |
949 ms |
154764 KB |
Output is correct |
43 |
Correct |
948 ms |
154628 KB |
Output is correct |
44 |
Correct |
952 ms |
154604 KB |
Output is correct |
45 |
Correct |
895 ms |
148400 KB |
Output is correct |
46 |
Correct |
627 ms |
109468 KB |
Output is correct |
47 |
Correct |
759 ms |
132992 KB |
Output is correct |
48 |
Correct |
1288 ms |
191192 KB |
Output is correct |
49 |
Correct |
1303 ms |
191788 KB |
Output is correct |
50 |
Correct |
628 ms |
93180 KB |
Output is correct |
51 |
Correct |
640 ms |
87380 KB |
Output is correct |
52 |
Correct |
1150 ms |
154836 KB |
Output is correct |
53 |
Correct |
1167 ms |
154916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
11212 KB |
Output is correct |
2 |
Correct |
8 ms |
9644 KB |
Output is correct |
3 |
Correct |
3 ms |
972 KB |
Output is correct |
4 |
Correct |
1 ms |
292 KB |
Output is correct |
5 |
Correct |
12 ms |
10316 KB |
Output is correct |
6 |
Correct |
11 ms |
10164 KB |
Output is correct |
7 |
Correct |
12 ms |
10456 KB |
Output is correct |
8 |
Correct |
10 ms |
9580 KB |
Output is correct |
9 |
Correct |
10 ms |
9420 KB |
Output is correct |
10 |
Correct |
1 ms |
336 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 |
2 ms |
1100 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 |
460 KB |
Output is correct |
7 |
Correct |
4127 ms |
441556 KB |
Output is correct |
8 |
Execution timed out |
5084 ms |
904448 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
3 ms |
1356 KB |
Output is correct |
3 |
Correct |
2 ms |
1356 KB |
Output is correct |
4 |
Correct |
3 ms |
1356 KB |
Output is correct |
5 |
Correct |
2 ms |
844 KB |
Output is correct |
6 |
Correct |
3 ms |
1356 KB |
Output is correct |
7 |
Correct |
2 ms |
1100 KB |
Output is correct |
8 |
Correct |
1 ms |
684 KB |
Output is correct |
9 |
Correct |
3 ms |
1324 KB |
Output is correct |
10 |
Correct |
2 ms |
1228 KB |
Output is correct |
11 |
Correct |
3 ms |
1228 KB |
Output is correct |
12 |
Correct |
2 ms |
1228 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
304 KB |
Output is correct |
15 |
Correct |
1 ms |
428 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
11 ms |
4164 KB |
Output is correct |
18 |
Correct |
11 ms |
4168 KB |
Output is correct |
19 |
Correct |
12 ms |
4156 KB |
Output is correct |
20 |
Correct |
10 ms |
3524 KB |
Output is correct |
21 |
Correct |
13 ms |
4036 KB |
Output is correct |
22 |
Correct |
13 ms |
3948 KB |
Output is correct |
23 |
Correct |
14 ms |
4160 KB |
Output is correct |
24 |
Correct |
6 ms |
2892 KB |
Output is correct |
25 |
Correct |
69 ms |
17708 KB |
Output is correct |
26 |
Correct |
71 ms |
17900 KB |
Output is correct |
27 |
Correct |
77 ms |
17932 KB |
Output is correct |
28 |
Correct |
63 ms |
13500 KB |
Output is correct |
29 |
Correct |
92 ms |
18268 KB |
Output is correct |
30 |
Correct |
92 ms |
18524 KB |
Output is correct |
31 |
Correct |
88 ms |
17824 KB |
Output is correct |
32 |
Correct |
85 ms |
17716 KB |
Output is correct |
33 |
Correct |
691 ms |
105124 KB |
Output is correct |
34 |
Correct |
645 ms |
105092 KB |
Output is correct |
35 |
Correct |
470 ms |
90284 KB |
Output is correct |
36 |
Correct |
462 ms |
90236 KB |
Output is correct |
37 |
Correct |
949 ms |
154764 KB |
Output is correct |
38 |
Correct |
948 ms |
154628 KB |
Output is correct |
39 |
Correct |
952 ms |
154604 KB |
Output is correct |
40 |
Correct |
895 ms |
148400 KB |
Output is correct |
41 |
Correct |
627 ms |
109468 KB |
Output is correct |
42 |
Correct |
759 ms |
132992 KB |
Output is correct |
43 |
Correct |
1288 ms |
191192 KB |
Output is correct |
44 |
Correct |
1303 ms |
191788 KB |
Output is correct |
45 |
Correct |
628 ms |
93180 KB |
Output is correct |
46 |
Correct |
640 ms |
87380 KB |
Output is correct |
47 |
Correct |
1150 ms |
154836 KB |
Output is correct |
48 |
Correct |
1167 ms |
154916 KB |
Output is correct |
49 |
Correct |
9 ms |
11212 KB |
Output is correct |
50 |
Correct |
8 ms |
9644 KB |
Output is correct |
51 |
Correct |
3 ms |
972 KB |
Output is correct |
52 |
Correct |
1 ms |
292 KB |
Output is correct |
53 |
Correct |
12 ms |
10316 KB |
Output is correct |
54 |
Correct |
11 ms |
10164 KB |
Output is correct |
55 |
Correct |
12 ms |
10456 KB |
Output is correct |
56 |
Correct |
10 ms |
9580 KB |
Output is correct |
57 |
Correct |
10 ms |
9420 KB |
Output is correct |
58 |
Correct |
1 ms |
336 KB |
Output is correct |
59 |
Correct |
1 ms |
332 KB |
Output is correct |
60 |
Correct |
1 ms |
460 KB |
Output is correct |
61 |
Correct |
4127 ms |
441556 KB |
Output is correct |
62 |
Execution timed out |
5084 ms |
904448 KB |
Time limit exceeded |
63 |
Halted |
0 ms |
0 KB |
- |