# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
291174 |
2020-09-04T20:07:49 Z |
thebes |
Rectangles (IOI19_rect) |
C++14 |
|
5000 ms |
516856 KB |
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define F first
#define S second
const int MN = 2505, MM = 13e6;
int N, M, C, i, j, x, y, h[MM], hp[MM], cnt, pre[MN], ds[MN], nxt[MN]; ll ans;
pii bnd[MM]; vi vec[MN], adj[MM], hid[MN];
map<pii,int> id; queue<pii> q[MN];
vector<pii> evt[MN];
pii hist[MN][MN];
inline void add(int l,int r,int pid,int x,bool col){
if(l==-1||r==-1) return;
if(!id.count({l,r})){
if(col){
id[{l,r}]=1;
evt[r-1].push_back({x,l+1});
}
else{
id[{l,r}]=++cnt;
bnd[cnt] = {l+1,r-1};
h[cnt] = x;
if(pid!=-1){
adj[cnt].push_back(pid);
hp[pid] = 1;
}
}
q[r-l].push({l,r});
}
else if(!col){
if(pid!=-1){
adj[id[{l,r}]].push_back(pid);
hp[pid] = 1;
}
}
}
map<int,int> mp;
inline void process(vi vec,int x,bool col){
C = (int)vec.size();
mp.clear();
for(int i=C-1;i>=0;i--){
auto it=mp.upper_bound(vec[i]);
if(it==mp.end()) nxt[i]=-1;
else nxt[i]=it->S;
while(mp.size()&&mp.begin()->F<=vec[i]) mp.erase(mp.begin());
mp[vec[i]]=i;
}
mp.clear();
for(int i=0;i<C;i++){
auto it=mp.upper_bound(vec[i]);
if(it==mp.end()) pre[i]=-1;
else pre[i]=it->S;
while(mp.size()&&mp.begin()->F<=vec[i]) mp.erase(mp.begin());
mp[vec[i]]=i;
}
id.clear();
queue<pii> hm; vector<pii> tmp;
for(int i=1;i<C-1;i++){
int l = pre[i], r = nxt[i];
if(l!=-1&&r!=-1) tmp.push_back({l,r});
}
sort(tmp.begin(),tmp.end(),[](pii i,pii j){return i.S-i.F<j.S-j.F;});
for(auto v : tmp) hm.push(v);
tmp.clear();
for(int i=0;i<=C;i++){
while(hm.size()&&hm.front().S-hm.front().F==i){
add(hm.front().F,hm.front().S,-1,x,col);
hm.pop();
}
while(q[i].size()){
pii cur = q[i].front(); q[i].pop();
int l, r;
if(vec[cur.F]==vec[cur.S]) l = pre[cur.F], r = nxt[cur.S];
else if(vec[cur.F]<vec[cur.S]) l = pre[cur.F], r = cur.S;
else l = cur.F, r = nxt[cur.S];
add(l,r,id[cur],x,col);
}
}
}
vi res;
inline void mrg(int x,int y){
if(x^y){
res.clear();
for(int i=0,j=0;i<(int)vec[x].size();i++){
while(j+1<(int)vec[y].size()&&vec[y][j]<vec[x][i]) j++;
if(j<vec[y].size()&&vec[x][i]==vec[y][j]) res.push_back(vec[x][i]);
}
vec[x].clear();
vec[y]=res;
}
}
int fnd(int x){return ds[x]=ds[x]==x?x:fnd(ds[x]);}
void dfs(int n){
for(auto v : adj[n]) dfs(v);
for(auto v : adj[n]) mrg(bnd[v].S, bnd[n].S);
int it = fnd(bnd[n].F);
while(it<M&&it<=bnd[n].S){
mrg(it,bnd[n].S);
ds[fnd(it)]=fnd(it+1);
it = fnd(it);
}
int p = upper_bound(vec[bnd[n].S].begin(),vec[bnd[n].S].end(),h[n])-vec[bnd[n].S].begin();
ans += vec[bnd[n].S].size()-p;
}
long long count_rectangles(vector<vector<int>> a){
vi col;
N = a.size(), M = a[0].size();
for(i=0;i<M;i++){
col.clear();
for(j=0;j<N;j++) col.push_back(a[j][i]);
process(col,i,1);
}
for(i=0;i<N;i++)
process(a[i],i,0);
for(i=1;i<=cnt;i++){
hid[h[i]].push_back(i);
}
memset(hist,-1,sizeof(hist));
for(i=0;i<N;i++){
for(j=0;j<M;j++) vec[j].clear(), ds[j]=j;
for(auto v : evt[i]) vec[v.F].push_back(v.S);
for(j=0;j<M;j++) sort(vec[j].begin(),vec[j].end());
for(auto v : hid[i]){
if(hist[bnd[v].F][bnd[v].S].F==i) h[v] = hist[bnd[v].F][bnd[v].S].S+1;
else h[v] = 1;
hist[bnd[v].F][bnd[v].S]={i+1,h[v]};
h[v] = i-h[v];
}
for(auto v : hid[i]){
if(hp[v]) continue;
dfs(v);
}
}
return ans;
}
Compilation message
rect.cpp: In function 'void mrg(int, int)':
rect.cpp:96:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | if(j<vec[y].size()&&vec[x][i]==vec[y][j]) res.push_back(vec[x][i]);
| ~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
232 ms |
356600 KB |
Output is correct |
2 |
Correct |
236 ms |
356728 KB |
Output is correct |
3 |
Correct |
232 ms |
356728 KB |
Output is correct |
4 |
Correct |
230 ms |
356856 KB |
Output is correct |
5 |
Correct |
229 ms |
356600 KB |
Output is correct |
6 |
Correct |
236 ms |
356600 KB |
Output is correct |
7 |
Correct |
232 ms |
356728 KB |
Output is correct |
8 |
Correct |
232 ms |
356600 KB |
Output is correct |
9 |
Correct |
240 ms |
356584 KB |
Output is correct |
10 |
Correct |
233 ms |
356600 KB |
Output is correct |
11 |
Correct |
232 ms |
356600 KB |
Output is correct |
12 |
Correct |
231 ms |
356600 KB |
Output is correct |
13 |
Correct |
232 ms |
356600 KB |
Output is correct |
14 |
Correct |
229 ms |
356728 KB |
Output is correct |
15 |
Correct |
232 ms |
356728 KB |
Output is correct |
16 |
Correct |
233 ms |
356600 KB |
Output is correct |
17 |
Correct |
231 ms |
356552 KB |
Output is correct |
18 |
Correct |
229 ms |
356728 KB |
Output is correct |
19 |
Correct |
231 ms |
356600 KB |
Output is correct |
20 |
Correct |
232 ms |
356600 KB |
Output is correct |
21 |
Correct |
232 ms |
356600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
232 ms |
356600 KB |
Output is correct |
2 |
Correct |
236 ms |
356728 KB |
Output is correct |
3 |
Correct |
232 ms |
356728 KB |
Output is correct |
4 |
Correct |
230 ms |
356856 KB |
Output is correct |
5 |
Correct |
229 ms |
356600 KB |
Output is correct |
6 |
Correct |
236 ms |
356600 KB |
Output is correct |
7 |
Correct |
232 ms |
356728 KB |
Output is correct |
8 |
Correct |
232 ms |
356600 KB |
Output is correct |
9 |
Correct |
240 ms |
356584 KB |
Output is correct |
10 |
Correct |
233 ms |
356600 KB |
Output is correct |
11 |
Correct |
232 ms |
356600 KB |
Output is correct |
12 |
Correct |
231 ms |
356600 KB |
Output is correct |
13 |
Correct |
232 ms |
356600 KB |
Output is correct |
14 |
Correct |
229 ms |
356728 KB |
Output is correct |
15 |
Correct |
232 ms |
356728 KB |
Output is correct |
16 |
Correct |
233 ms |
356600 KB |
Output is correct |
17 |
Correct |
241 ms |
357112 KB |
Output is correct |
18 |
Correct |
241 ms |
357092 KB |
Output is correct |
19 |
Correct |
238 ms |
357112 KB |
Output is correct |
20 |
Correct |
234 ms |
356728 KB |
Output is correct |
21 |
Correct |
239 ms |
357112 KB |
Output is correct |
22 |
Correct |
244 ms |
356988 KB |
Output is correct |
23 |
Correct |
239 ms |
356984 KB |
Output is correct |
24 |
Correct |
237 ms |
356772 KB |
Output is correct |
25 |
Correct |
231 ms |
356552 KB |
Output is correct |
26 |
Correct |
229 ms |
356728 KB |
Output is correct |
27 |
Correct |
231 ms |
356600 KB |
Output is correct |
28 |
Correct |
232 ms |
356600 KB |
Output is correct |
29 |
Correct |
232 ms |
356600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
232 ms |
356600 KB |
Output is correct |
2 |
Correct |
236 ms |
356728 KB |
Output is correct |
3 |
Correct |
232 ms |
356728 KB |
Output is correct |
4 |
Correct |
230 ms |
356856 KB |
Output is correct |
5 |
Correct |
229 ms |
356600 KB |
Output is correct |
6 |
Correct |
236 ms |
356600 KB |
Output is correct |
7 |
Correct |
232 ms |
356728 KB |
Output is correct |
8 |
Correct |
232 ms |
356600 KB |
Output is correct |
9 |
Correct |
240 ms |
356584 KB |
Output is correct |
10 |
Correct |
233 ms |
356600 KB |
Output is correct |
11 |
Correct |
232 ms |
356600 KB |
Output is correct |
12 |
Correct |
231 ms |
356600 KB |
Output is correct |
13 |
Correct |
232 ms |
356600 KB |
Output is correct |
14 |
Correct |
229 ms |
356728 KB |
Output is correct |
15 |
Correct |
232 ms |
356728 KB |
Output is correct |
16 |
Correct |
233 ms |
356600 KB |
Output is correct |
17 |
Correct |
241 ms |
357112 KB |
Output is correct |
18 |
Correct |
241 ms |
357092 KB |
Output is correct |
19 |
Correct |
238 ms |
357112 KB |
Output is correct |
20 |
Correct |
234 ms |
356728 KB |
Output is correct |
21 |
Correct |
239 ms |
357112 KB |
Output is correct |
22 |
Correct |
244 ms |
356988 KB |
Output is correct |
23 |
Correct |
239 ms |
356984 KB |
Output is correct |
24 |
Correct |
237 ms |
356772 KB |
Output is correct |
25 |
Correct |
277 ms |
359668 KB |
Output is correct |
26 |
Correct |
281 ms |
359668 KB |
Output is correct |
27 |
Correct |
276 ms |
359540 KB |
Output is correct |
28 |
Correct |
261 ms |
357624 KB |
Output is correct |
29 |
Correct |
294 ms |
359028 KB |
Output is correct |
30 |
Correct |
297 ms |
358904 KB |
Output is correct |
31 |
Correct |
291 ms |
358908 KB |
Output is correct |
32 |
Correct |
291 ms |
358776 KB |
Output is correct |
33 |
Correct |
231 ms |
356552 KB |
Output is correct |
34 |
Correct |
229 ms |
356728 KB |
Output is correct |
35 |
Correct |
231 ms |
356600 KB |
Output is correct |
36 |
Correct |
232 ms |
356600 KB |
Output is correct |
37 |
Correct |
232 ms |
356600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
232 ms |
356600 KB |
Output is correct |
2 |
Correct |
236 ms |
356728 KB |
Output is correct |
3 |
Correct |
232 ms |
356728 KB |
Output is correct |
4 |
Correct |
230 ms |
356856 KB |
Output is correct |
5 |
Correct |
229 ms |
356600 KB |
Output is correct |
6 |
Correct |
236 ms |
356600 KB |
Output is correct |
7 |
Correct |
232 ms |
356728 KB |
Output is correct |
8 |
Correct |
232 ms |
356600 KB |
Output is correct |
9 |
Correct |
240 ms |
356584 KB |
Output is correct |
10 |
Correct |
233 ms |
356600 KB |
Output is correct |
11 |
Correct |
232 ms |
356600 KB |
Output is correct |
12 |
Correct |
231 ms |
356600 KB |
Output is correct |
13 |
Correct |
232 ms |
356600 KB |
Output is correct |
14 |
Correct |
229 ms |
356728 KB |
Output is correct |
15 |
Correct |
232 ms |
356728 KB |
Output is correct |
16 |
Correct |
233 ms |
356600 KB |
Output is correct |
17 |
Correct |
241 ms |
357112 KB |
Output is correct |
18 |
Correct |
241 ms |
357092 KB |
Output is correct |
19 |
Correct |
238 ms |
357112 KB |
Output is correct |
20 |
Correct |
234 ms |
356728 KB |
Output is correct |
21 |
Correct |
239 ms |
357112 KB |
Output is correct |
22 |
Correct |
244 ms |
356988 KB |
Output is correct |
23 |
Correct |
239 ms |
356984 KB |
Output is correct |
24 |
Correct |
237 ms |
356772 KB |
Output is correct |
25 |
Correct |
277 ms |
359668 KB |
Output is correct |
26 |
Correct |
281 ms |
359668 KB |
Output is correct |
27 |
Correct |
276 ms |
359540 KB |
Output is correct |
28 |
Correct |
261 ms |
357624 KB |
Output is correct |
29 |
Correct |
294 ms |
359028 KB |
Output is correct |
30 |
Correct |
297 ms |
358904 KB |
Output is correct |
31 |
Correct |
291 ms |
358908 KB |
Output is correct |
32 |
Correct |
291 ms |
358776 KB |
Output is correct |
33 |
Correct |
635 ms |
377964 KB |
Output is correct |
34 |
Correct |
645 ms |
377976 KB |
Output is correct |
35 |
Correct |
637 ms |
376596 KB |
Output is correct |
36 |
Correct |
646 ms |
376440 KB |
Output is correct |
37 |
Correct |
805 ms |
393040 KB |
Output is correct |
38 |
Correct |
799 ms |
393140 KB |
Output is correct |
39 |
Correct |
806 ms |
393136 KB |
Output is correct |
40 |
Correct |
782 ms |
390996 KB |
Output is correct |
41 |
Correct |
508 ms |
364280 KB |
Output is correct |
42 |
Correct |
626 ms |
369232 KB |
Output is correct |
43 |
Correct |
1077 ms |
386496 KB |
Output is correct |
44 |
Correct |
1091 ms |
386808 KB |
Output is correct |
45 |
Correct |
648 ms |
371576 KB |
Output is correct |
46 |
Correct |
653 ms |
371704 KB |
Output is correct |
47 |
Correct |
1045 ms |
384684 KB |
Output is correct |
48 |
Correct |
1050 ms |
384960 KB |
Output is correct |
49 |
Correct |
231 ms |
356552 KB |
Output is correct |
50 |
Correct |
229 ms |
356728 KB |
Output is correct |
51 |
Correct |
231 ms |
356600 KB |
Output is correct |
52 |
Correct |
232 ms |
356600 KB |
Output is correct |
53 |
Correct |
232 ms |
356600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
239 ms |
357748 KB |
Output is correct |
2 |
Correct |
241 ms |
357368 KB |
Output is correct |
3 |
Correct |
234 ms |
356732 KB |
Output is correct |
4 |
Correct |
235 ms |
356776 KB |
Output is correct |
5 |
Correct |
239 ms |
357240 KB |
Output is correct |
6 |
Correct |
241 ms |
357240 KB |
Output is correct |
7 |
Correct |
241 ms |
357112 KB |
Output is correct |
8 |
Correct |
241 ms |
357228 KB |
Output is correct |
9 |
Correct |
241 ms |
357240 KB |
Output is correct |
10 |
Correct |
233 ms |
356984 KB |
Output is correct |
11 |
Correct |
237 ms |
357112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
236 ms |
356700 KB |
Output is correct |
2 |
Correct |
1917 ms |
402712 KB |
Output is correct |
3 |
Correct |
3940 ms |
455344 KB |
Output is correct |
4 |
Correct |
3983 ms |
456156 KB |
Output is correct |
5 |
Correct |
3953 ms |
456156 KB |
Output is correct |
6 |
Correct |
1078 ms |
380824 KB |
Output is correct |
7 |
Correct |
1862 ms |
402808 KB |
Output is correct |
8 |
Correct |
1964 ms |
405772 KB |
Output is correct |
9 |
Correct |
231 ms |
356552 KB |
Output is correct |
10 |
Correct |
229 ms |
356728 KB |
Output is correct |
11 |
Correct |
231 ms |
356600 KB |
Output is correct |
12 |
Correct |
232 ms |
356600 KB |
Output is correct |
13 |
Correct |
232 ms |
356600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
232 ms |
356600 KB |
Output is correct |
2 |
Correct |
236 ms |
356728 KB |
Output is correct |
3 |
Correct |
232 ms |
356728 KB |
Output is correct |
4 |
Correct |
230 ms |
356856 KB |
Output is correct |
5 |
Correct |
229 ms |
356600 KB |
Output is correct |
6 |
Correct |
236 ms |
356600 KB |
Output is correct |
7 |
Correct |
232 ms |
356728 KB |
Output is correct |
8 |
Correct |
232 ms |
356600 KB |
Output is correct |
9 |
Correct |
240 ms |
356584 KB |
Output is correct |
10 |
Correct |
233 ms |
356600 KB |
Output is correct |
11 |
Correct |
232 ms |
356600 KB |
Output is correct |
12 |
Correct |
231 ms |
356600 KB |
Output is correct |
13 |
Correct |
232 ms |
356600 KB |
Output is correct |
14 |
Correct |
229 ms |
356728 KB |
Output is correct |
15 |
Correct |
232 ms |
356728 KB |
Output is correct |
16 |
Correct |
233 ms |
356600 KB |
Output is correct |
17 |
Correct |
241 ms |
357112 KB |
Output is correct |
18 |
Correct |
241 ms |
357092 KB |
Output is correct |
19 |
Correct |
238 ms |
357112 KB |
Output is correct |
20 |
Correct |
234 ms |
356728 KB |
Output is correct |
21 |
Correct |
239 ms |
357112 KB |
Output is correct |
22 |
Correct |
244 ms |
356988 KB |
Output is correct |
23 |
Correct |
239 ms |
356984 KB |
Output is correct |
24 |
Correct |
237 ms |
356772 KB |
Output is correct |
25 |
Correct |
277 ms |
359668 KB |
Output is correct |
26 |
Correct |
281 ms |
359668 KB |
Output is correct |
27 |
Correct |
276 ms |
359540 KB |
Output is correct |
28 |
Correct |
261 ms |
357624 KB |
Output is correct |
29 |
Correct |
294 ms |
359028 KB |
Output is correct |
30 |
Correct |
297 ms |
358904 KB |
Output is correct |
31 |
Correct |
291 ms |
358908 KB |
Output is correct |
32 |
Correct |
291 ms |
358776 KB |
Output is correct |
33 |
Correct |
635 ms |
377964 KB |
Output is correct |
34 |
Correct |
645 ms |
377976 KB |
Output is correct |
35 |
Correct |
637 ms |
376596 KB |
Output is correct |
36 |
Correct |
646 ms |
376440 KB |
Output is correct |
37 |
Correct |
805 ms |
393040 KB |
Output is correct |
38 |
Correct |
799 ms |
393140 KB |
Output is correct |
39 |
Correct |
806 ms |
393136 KB |
Output is correct |
40 |
Correct |
782 ms |
390996 KB |
Output is correct |
41 |
Correct |
508 ms |
364280 KB |
Output is correct |
42 |
Correct |
626 ms |
369232 KB |
Output is correct |
43 |
Correct |
1077 ms |
386496 KB |
Output is correct |
44 |
Correct |
1091 ms |
386808 KB |
Output is correct |
45 |
Correct |
648 ms |
371576 KB |
Output is correct |
46 |
Correct |
653 ms |
371704 KB |
Output is correct |
47 |
Correct |
1045 ms |
384684 KB |
Output is correct |
48 |
Correct |
1050 ms |
384960 KB |
Output is correct |
49 |
Correct |
239 ms |
357748 KB |
Output is correct |
50 |
Correct |
241 ms |
357368 KB |
Output is correct |
51 |
Correct |
234 ms |
356732 KB |
Output is correct |
52 |
Correct |
235 ms |
356776 KB |
Output is correct |
53 |
Correct |
239 ms |
357240 KB |
Output is correct |
54 |
Correct |
241 ms |
357240 KB |
Output is correct |
55 |
Correct |
241 ms |
357112 KB |
Output is correct |
56 |
Correct |
241 ms |
357228 KB |
Output is correct |
57 |
Correct |
241 ms |
357240 KB |
Output is correct |
58 |
Correct |
233 ms |
356984 KB |
Output is correct |
59 |
Correct |
237 ms |
357112 KB |
Output is correct |
60 |
Correct |
236 ms |
356700 KB |
Output is correct |
61 |
Correct |
1917 ms |
402712 KB |
Output is correct |
62 |
Correct |
3940 ms |
455344 KB |
Output is correct |
63 |
Correct |
3983 ms |
456156 KB |
Output is correct |
64 |
Correct |
3953 ms |
456156 KB |
Output is correct |
65 |
Correct |
1078 ms |
380824 KB |
Output is correct |
66 |
Correct |
1862 ms |
402808 KB |
Output is correct |
67 |
Correct |
1964 ms |
405772 KB |
Output is correct |
68 |
Execution timed out |
5108 ms |
516856 KB |
Time limit exceeded |
69 |
Halted |
0 ms |
0 KB |
- |