# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
199532 |
2020-02-02T00:18:24 Z |
medk |
Rectangles (IOI19_rect) |
C++14 |
|
5000 ms |
273640 KB |
#include <bits/stdc++.h>
#include "rect.h"
#define ll long long
#define pb push_back
#define x first
#define y second
using namespace std;
map<pair<int,int>,set<pair<int,int>>> mp,mp2;
vector<int> bit(3000);
void upd(int x, int val)
{
x++;
for(;x<3000;x+=(x&-x))
bit[x]+=val;
}
int getpre(int x)
{
x++;
int ret=0;
for(;x>0;x-=(x&-x))
ret+=bit[x];
return ret;
}
ll count_rectangles(vector<vector<int>> a)
{
//freopen("test.in","r",stdin);
//ios::sync_with_stdio(0); cin.tie(0);
int n=a.size(), m=a[0].size();
for(int i=0;i<n;i++)
{
fill(bit.begin(),bit.end(),0);
vector<pair<int,int>> vp;
for(int j=0;j<m;j++) vp.pb({a[i][j],j});
sort(vp.begin(),vp.end());
for(int j=0;j<m;j++)
{
upd(vp[j].y,1);
int l=vp[j].y, r=m-1;
while(l<r)
{
int md=(l+r)/2+1;
if(getpre(md)-getpre(vp[j].y)==md-vp[j].y) l=md;
else r=md-1;
}
int l2=0, r2=vp[j].y;
while(l2<r2)
{
int md=(l2+r2)/2;
if(getpre(vp[j].y)-getpre(md-1)==vp[j].y-md+1) r2=md;
else l2=md+1;
}
if(l2==0 || l==m-1) continue;
if(a[i][l+1]==vp[j].x || a[i][l2-1]==vp[j].x) continue;
int num=1;
if(mp.count({i-1,l2-1}))
{
auto it = mp[{i-1,l2-1}].lower_bound({l+1,0});
if(it!=mp[{i-1,l2-1}].end()) if((*it).x==l+1) num+=(*it).y;
}
mp[{i,l2-1}].insert({l+1,num});
num=1;
if(mp.count({i-1,l+1}))
{
auto it = mp[{i-1,l+1}].lower_bound({l2-1,0});
if(it!=mp[{i-1,l+1}].end()) if((*it).x==l2-1) num+=(*it).y;
}
mp[{i,l+1}].insert({l2-1,num});
}
}
ll ans=0;
for(int i=1;i<m-1;i++)
{
fill(bit.begin(),bit.end(),0);
vector<pair<int,int>> vp;
for(int j=0;j<n;j++) vp.pb({a[j][i],j});
sort(vp.begin(),vp.end());
for(int j=0;j<n;j++)
{
upd(vp[j].y,1);
int l=vp[j].y, r=n-1;
while(l<r)
{
int md=(l+r)/2+1;
if(getpre(md)-getpre(vp[j].y)==md-vp[j].y) l=md;
else r=md-1;
}
int l2=0, r2=vp[j].y;
while(l2<r2)
{
int md=(l2+r2)/2;
if(getpre(vp[j].y)-getpre(md-1)==vp[j].y-md+1) r2=md;
else l2=md+1;
}
if(l2==0 || l==n-1) continue;
if(a[l+1][i]==vp[j].x || a[l2-1][i]==vp[j].x) continue;
int num=1;
if(mp2.count({l2-1,i-1}))
{
auto it = mp2[{l2-1,i-1}].lower_bound({l+1,0});
if(it!=mp2[{l2-1,i-1}].end()) if((*it).x==l+1) num+=(*it).y;
}
mp2[{l2-1,i}].insert({l+1,num});
num=1;
if(mp2.count({l+1,i-1}))
{
auto it = mp2[{l+1,i-1}].lower_bound({l2-1,0});
if(it!=mp2[{l+1,i-1}].end()) if((*it).x==l2-1) num+=(*it).y;
}
mp2[{l+1,i}].insert({l2-1,num});
auto it = mp[{l,i+1}].lower_bound({i-num,l-l2+1});
for(;it!=mp[{l,i+1}].end();it++)
{
if((*it).x>i+1) break;
if((*it).y>=l-l2+1) ans++;
}
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
7 ms |
632 KB |
Output is correct |
3 |
Correct |
7 ms |
632 KB |
Output is correct |
4 |
Correct |
7 ms |
632 KB |
Output is correct |
5 |
Correct |
6 ms |
376 KB |
Output is correct |
6 |
Correct |
7 ms |
504 KB |
Output is correct |
7 |
Correct |
6 ms |
376 KB |
Output is correct |
8 |
Correct |
6 ms |
376 KB |
Output is correct |
9 |
Correct |
7 ms |
504 KB |
Output is correct |
10 |
Correct |
7 ms |
504 KB |
Output is correct |
11 |
Correct |
7 ms |
632 KB |
Output is correct |
12 |
Correct |
7 ms |
508 KB |
Output is correct |
13 |
Correct |
6 ms |
256 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
5 ms |
256 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
248 KB |
Output is correct |
18 |
Correct |
5 ms |
256 KB |
Output is correct |
19 |
Correct |
6 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
7 ms |
632 KB |
Output is correct |
3 |
Correct |
7 ms |
632 KB |
Output is correct |
4 |
Correct |
7 ms |
632 KB |
Output is correct |
5 |
Correct |
6 ms |
376 KB |
Output is correct |
6 |
Correct |
7 ms |
504 KB |
Output is correct |
7 |
Correct |
6 ms |
376 KB |
Output is correct |
8 |
Correct |
6 ms |
376 KB |
Output is correct |
9 |
Correct |
7 ms |
504 KB |
Output is correct |
10 |
Correct |
7 ms |
504 KB |
Output is correct |
11 |
Correct |
7 ms |
632 KB |
Output is correct |
12 |
Correct |
7 ms |
508 KB |
Output is correct |
13 |
Correct |
6 ms |
256 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
5 ms |
256 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
20 ms |
2680 KB |
Output is correct |
18 |
Correct |
20 ms |
2680 KB |
Output is correct |
19 |
Correct |
20 ms |
2680 KB |
Output is correct |
20 |
Correct |
15 ms |
1400 KB |
Output is correct |
21 |
Correct |
23 ms |
2296 KB |
Output is correct |
22 |
Correct |
22 ms |
2296 KB |
Output is correct |
23 |
Correct |
22 ms |
2168 KB |
Output is correct |
24 |
Correct |
12 ms |
1144 KB |
Output is correct |
25 |
Correct |
5 ms |
248 KB |
Output is correct |
26 |
Correct |
5 ms |
256 KB |
Output is correct |
27 |
Correct |
6 ms |
376 KB |
Output is correct |
28 |
Correct |
5 ms |
376 KB |
Output is correct |
29 |
Correct |
5 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
7 ms |
632 KB |
Output is correct |
3 |
Correct |
7 ms |
632 KB |
Output is correct |
4 |
Correct |
7 ms |
632 KB |
Output is correct |
5 |
Correct |
6 ms |
376 KB |
Output is correct |
6 |
Correct |
7 ms |
504 KB |
Output is correct |
7 |
Correct |
6 ms |
376 KB |
Output is correct |
8 |
Correct |
6 ms |
376 KB |
Output is correct |
9 |
Correct |
7 ms |
504 KB |
Output is correct |
10 |
Correct |
7 ms |
504 KB |
Output is correct |
11 |
Correct |
7 ms |
632 KB |
Output is correct |
12 |
Correct |
7 ms |
508 KB |
Output is correct |
13 |
Correct |
6 ms |
256 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
5 ms |
256 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
20 ms |
2680 KB |
Output is correct |
18 |
Correct |
20 ms |
2680 KB |
Output is correct |
19 |
Correct |
20 ms |
2680 KB |
Output is correct |
20 |
Correct |
15 ms |
1400 KB |
Output is correct |
21 |
Correct |
23 ms |
2296 KB |
Output is correct |
22 |
Correct |
22 ms |
2296 KB |
Output is correct |
23 |
Correct |
22 ms |
2168 KB |
Output is correct |
24 |
Correct |
12 ms |
1144 KB |
Output is correct |
25 |
Correct |
117 ms |
15480 KB |
Output is correct |
26 |
Correct |
116 ms |
15480 KB |
Output is correct |
27 |
Correct |
117 ms |
15480 KB |
Output is correct |
28 |
Correct |
78 ms |
7544 KB |
Output is correct |
29 |
Correct |
154 ms |
13048 KB |
Output is correct |
30 |
Correct |
156 ms |
13176 KB |
Output is correct |
31 |
Correct |
144 ms |
12280 KB |
Output is correct |
32 |
Correct |
149 ms |
12108 KB |
Output is correct |
33 |
Correct |
5 ms |
248 KB |
Output is correct |
34 |
Correct |
5 ms |
256 KB |
Output is correct |
35 |
Correct |
6 ms |
376 KB |
Output is correct |
36 |
Correct |
5 ms |
376 KB |
Output is correct |
37 |
Correct |
5 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
7 ms |
632 KB |
Output is correct |
3 |
Correct |
7 ms |
632 KB |
Output is correct |
4 |
Correct |
7 ms |
632 KB |
Output is correct |
5 |
Correct |
6 ms |
376 KB |
Output is correct |
6 |
Correct |
7 ms |
504 KB |
Output is correct |
7 |
Correct |
6 ms |
376 KB |
Output is correct |
8 |
Correct |
6 ms |
376 KB |
Output is correct |
9 |
Correct |
7 ms |
504 KB |
Output is correct |
10 |
Correct |
7 ms |
504 KB |
Output is correct |
11 |
Correct |
7 ms |
632 KB |
Output is correct |
12 |
Correct |
7 ms |
508 KB |
Output is correct |
13 |
Correct |
6 ms |
256 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
5 ms |
256 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
20 ms |
2680 KB |
Output is correct |
18 |
Correct |
20 ms |
2680 KB |
Output is correct |
19 |
Correct |
20 ms |
2680 KB |
Output is correct |
20 |
Correct |
15 ms |
1400 KB |
Output is correct |
21 |
Correct |
23 ms |
2296 KB |
Output is correct |
22 |
Correct |
22 ms |
2296 KB |
Output is correct |
23 |
Correct |
22 ms |
2168 KB |
Output is correct |
24 |
Correct |
12 ms |
1144 KB |
Output is correct |
25 |
Correct |
117 ms |
15480 KB |
Output is correct |
26 |
Correct |
116 ms |
15480 KB |
Output is correct |
27 |
Correct |
117 ms |
15480 KB |
Output is correct |
28 |
Correct |
78 ms |
7544 KB |
Output is correct |
29 |
Correct |
154 ms |
13048 KB |
Output is correct |
30 |
Correct |
156 ms |
13176 KB |
Output is correct |
31 |
Correct |
144 ms |
12280 KB |
Output is correct |
32 |
Correct |
149 ms |
12108 KB |
Output is correct |
33 |
Correct |
1034 ms |
95992 KB |
Output is correct |
34 |
Correct |
913 ms |
95980 KB |
Output is correct |
35 |
Correct |
1359 ms |
118880 KB |
Output is correct |
36 |
Correct |
1234 ms |
119000 KB |
Output is correct |
37 |
Correct |
1807 ms |
187744 KB |
Output is correct |
38 |
Correct |
1797 ms |
187456 KB |
Output is correct |
39 |
Correct |
1798 ms |
187792 KB |
Output is correct |
40 |
Correct |
1651 ms |
175352 KB |
Output is correct |
41 |
Correct |
981 ms |
67340 KB |
Output is correct |
42 |
Correct |
1355 ms |
90288 KB |
Output is correct |
43 |
Correct |
3083 ms |
160244 KB |
Output is correct |
44 |
Correct |
3079 ms |
161396 KB |
Output is correct |
45 |
Correct |
1355 ms |
80424 KB |
Output is correct |
46 |
Correct |
1242 ms |
80632 KB |
Output is correct |
47 |
Correct |
2871 ms |
148360 KB |
Output is correct |
48 |
Correct |
2843 ms |
148704 KB |
Output is correct |
49 |
Correct |
5 ms |
248 KB |
Output is correct |
50 |
Correct |
5 ms |
256 KB |
Output is correct |
51 |
Correct |
6 ms |
376 KB |
Output is correct |
52 |
Correct |
5 ms |
376 KB |
Output is correct |
53 |
Correct |
5 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
2424 KB |
Output is correct |
2 |
Correct |
21 ms |
2168 KB |
Output is correct |
3 |
Correct |
12 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
21 ms |
1784 KB |
Output is correct |
6 |
Correct |
22 ms |
1784 KB |
Output is correct |
7 |
Correct |
22 ms |
1912 KB |
Output is correct |
8 |
Correct |
21 ms |
1784 KB |
Output is correct |
9 |
Correct |
21 ms |
1656 KB |
Output is correct |
10 |
Correct |
11 ms |
760 KB |
Output is correct |
11 |
Correct |
16 ms |
1144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Execution timed out |
5301 ms |
273640 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
7 ms |
632 KB |
Output is correct |
3 |
Correct |
7 ms |
632 KB |
Output is correct |
4 |
Correct |
7 ms |
632 KB |
Output is correct |
5 |
Correct |
6 ms |
376 KB |
Output is correct |
6 |
Correct |
7 ms |
504 KB |
Output is correct |
7 |
Correct |
6 ms |
376 KB |
Output is correct |
8 |
Correct |
6 ms |
376 KB |
Output is correct |
9 |
Correct |
7 ms |
504 KB |
Output is correct |
10 |
Correct |
7 ms |
504 KB |
Output is correct |
11 |
Correct |
7 ms |
632 KB |
Output is correct |
12 |
Correct |
7 ms |
508 KB |
Output is correct |
13 |
Correct |
6 ms |
256 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
5 ms |
256 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
20 ms |
2680 KB |
Output is correct |
18 |
Correct |
20 ms |
2680 KB |
Output is correct |
19 |
Correct |
20 ms |
2680 KB |
Output is correct |
20 |
Correct |
15 ms |
1400 KB |
Output is correct |
21 |
Correct |
23 ms |
2296 KB |
Output is correct |
22 |
Correct |
22 ms |
2296 KB |
Output is correct |
23 |
Correct |
22 ms |
2168 KB |
Output is correct |
24 |
Correct |
12 ms |
1144 KB |
Output is correct |
25 |
Correct |
117 ms |
15480 KB |
Output is correct |
26 |
Correct |
116 ms |
15480 KB |
Output is correct |
27 |
Correct |
117 ms |
15480 KB |
Output is correct |
28 |
Correct |
78 ms |
7544 KB |
Output is correct |
29 |
Correct |
154 ms |
13048 KB |
Output is correct |
30 |
Correct |
156 ms |
13176 KB |
Output is correct |
31 |
Correct |
144 ms |
12280 KB |
Output is correct |
32 |
Correct |
149 ms |
12108 KB |
Output is correct |
33 |
Correct |
1034 ms |
95992 KB |
Output is correct |
34 |
Correct |
913 ms |
95980 KB |
Output is correct |
35 |
Correct |
1359 ms |
118880 KB |
Output is correct |
36 |
Correct |
1234 ms |
119000 KB |
Output is correct |
37 |
Correct |
1807 ms |
187744 KB |
Output is correct |
38 |
Correct |
1797 ms |
187456 KB |
Output is correct |
39 |
Correct |
1798 ms |
187792 KB |
Output is correct |
40 |
Correct |
1651 ms |
175352 KB |
Output is correct |
41 |
Correct |
981 ms |
67340 KB |
Output is correct |
42 |
Correct |
1355 ms |
90288 KB |
Output is correct |
43 |
Correct |
3083 ms |
160244 KB |
Output is correct |
44 |
Correct |
3079 ms |
161396 KB |
Output is correct |
45 |
Correct |
1355 ms |
80424 KB |
Output is correct |
46 |
Correct |
1242 ms |
80632 KB |
Output is correct |
47 |
Correct |
2871 ms |
148360 KB |
Output is correct |
48 |
Correct |
2843 ms |
148704 KB |
Output is correct |
49 |
Correct |
23 ms |
2424 KB |
Output is correct |
50 |
Correct |
21 ms |
2168 KB |
Output is correct |
51 |
Correct |
12 ms |
376 KB |
Output is correct |
52 |
Correct |
5 ms |
376 KB |
Output is correct |
53 |
Correct |
21 ms |
1784 KB |
Output is correct |
54 |
Correct |
22 ms |
1784 KB |
Output is correct |
55 |
Correct |
22 ms |
1912 KB |
Output is correct |
56 |
Correct |
21 ms |
1784 KB |
Output is correct |
57 |
Correct |
21 ms |
1656 KB |
Output is correct |
58 |
Correct |
11 ms |
760 KB |
Output is correct |
59 |
Correct |
16 ms |
1144 KB |
Output is correct |
60 |
Correct |
5 ms |
376 KB |
Output is correct |
61 |
Execution timed out |
5301 ms |
273640 KB |
Time limit exceeded |
62 |
Halted |
0 ms |
0 KB |
- |