12574 | 2024-12-23 18:12:19 | 4rt3xp0 | 2015. december | cpp17 | Accepted | 16ms | 792 KiB |
#include<bits/stdc++.h>
using namespace std;
vector<bool> visible(10001,0);
struct box{
int x1,y1,x2,y2,id;
};
void f(const vector<box> &v, bool x=false){
int N=100489,SQRT=317;
vector<bool> a(N,0),b(SQRT,0); vector<int> sumb(SQRT,0);
for(const box &box: v){
int l,r,sum=0;
if(x){
l=box.x1; r=box.x2;
}
else{
l=box.y1; r=box.y2;
}
r--;
for(int i=l;i<=r;){
if(i%SQRT==0 && i+SQRT-1<=r){
if(!b[i/SQRT]){
b[i/SQRT]=1;
visible[box.id]=1;
}
i+=SQRT;
}
else{
if(!a[i]){
a[i]=1; sumb[i/SQRT]++; if(sumb[i/SQRT]==SQRT) b[i/SQRT]=1;
visible[box.id]=1;
}
i++;
}
}
}
}
int main(){
int n,m,k,id=0,cnt=0; cin >> n >> m >> k;
vector<box> v(k);
for(box &i: v){
cin >> i.x1 >> i.y1 >> i.x2 >> i.y2;
i.id=++id;
}
sort(v.begin(),v.end(),[](const box &l, const box &r){return l.x1<r.x1;}); f(v);
sort(v.begin(),v.end(),[](const box &l, const box &r){return l.x2>r.x2;}); f(v);
sort(v.begin(),v.end(),[](const box &l, const box &r){return l.y1<r.y1;}); f(v,true);
sort(v.begin(),v.end(),[](const box &l, const box &r){return l.y2>r.y2;}); f(v,true);
// for(int i=1;i<=k;i++) if(!visible[i]) cout << i << '\n';
for(int i=1;i<=k;i++) if(!visible[i]) cnt++;
cout << cnt;
}
3
Expected output:3
Checker output:ok 1 number(s): "3"
11
Expected output:11
Checker output:ok 1 number(s): "11"
3
Expected output:3
Checker output:ok 1 number(s): "3"
0
Expected output:0
Checker output:ok 1 number(s): "0"
62
Expected output:62
Checker output:ok 1 number(s): "62"
174
Expected output:174
Checker output:ok 1 number(s): "174"
0
Expected output:0
Checker output:ok 1 number(s): "0"
0
Expected output:0
Checker output:ok 1 number(s): "0"
4
Expected output:4
Checker output:ok 1 number(s): "4"
569
Expected output:569
Checker output:ok 1 number(s): "569"
0
Expected output:0
Checker output:ok 1 number(s): "0"
0
Expected output:0
Checker output:ok 1 number(s): "0"
0
Expected output:0
Checker output:ok 1 number(s): "0"
0
Expected output:0
Checker output:ok 1 number(s): "0"
0
Expected output:0
Checker output:ok 1 number(s): "0"
14
Expected output:14
Checker output:ok 1 number(s): "14"
1
Expected output:1
Checker output:ok 1 number(s): "1"
6
Expected output:6
Checker output:ok 1 number(s): "6"
8
Expected output:8
Checker output:ok 1 number(s): "8"
0
Expected output:0
Checker output:ok 1 number(s): "0"
0
Expected output:0
Checker output:ok 1 number(s): "0"
2
Expected output:2
Checker output:ok 1 number(s): "2"
0
Expected output:0
Checker output:ok 1 number(s): "0"