QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#644341 | #4671. Independent Rectangles | cjx | WA | 1ms | 6048kb | C++20 | 2.0kb | 2024-10-16 13:24:12 | 2024-10-16 13:24:12 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
long long read(){
long long x=0,f=1;char ch=getchar();
while(!isdigit(ch))
{if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
void write(long long x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
const int N=1e4+10;
int n;
struct Node{
int x1,y1,x2,y2;
}a[N];
int b[N][4];
bitset<N>s[N],zy[N];
int id[N],di[N],k;
bool cmp1(int p,int q){
return b[p][k]<b[q][k];
}
bool cmp2(int p,int q){
return b[p][k]>b[q][k];
}
void solve(int n){
for(int i=1;i<=n;i++)id[i]=di[i]=i;
for(int i=1;i<=n;i++)s[i].set();
k=0;sort(id+1,id+n+1,cmp1);
k=2;sort(di+1,di+n+1,cmp1);
for(int i=1;i<=n;i++)zy[i]=zy[i-1],zy[i].set(id[i]);
for(int i=1,j=0;i<=n;i++){
while(j+1<=n&&b[id[j+1]][0]<b[di[i]][2])j++;
s[di[i]]&=zy[j];
}
k=2;sort(id+1,id+n+1,cmp2);
k=0;sort(di+1,di+n+1,cmp2);
for(int i=1;i<=n;i++)zy[i]=zy[i-1],zy[i].set(id[i]);
for(int i=1,j=0;i<=n;i++){
while(j+1<=n&&b[id[j+1]][2]>b[di[i]][0])j++;
s[di[i]]&=zy[j];
}
k=1;sort(id+1,id+n+1,cmp1);
k=3;sort(di+1,di+n+1,cmp1);
for(int i=1;i<=n;i++)zy[i]=zy[i-1],zy[i].set(id[i]);
for(int i=1,j=0;i<=n;i++){
while(j+1<=n&&b[id[j+1]][1]<b[di[i]][3])j++;
s[di[i]]&=zy[j];
}
k=3;sort(id+1,id+n+1,cmp2);
k=1;sort(di+1,di+n+1,cmp2);
for(int i=1;i<=n;i++)zy[i]=zy[i-1],zy[i].set(id[i]);
for(int i=1,j=0;i<=n;i++){
while(j+1<=n&&b[id[j+1]][3]>b[di[i]][1])j++;
s[di[i]]&=zy[j];
}
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=read();
for(int i=1;i<=n;i++){
b[i][0]=a[i].x1=read();
b[i][1]=a[i].y1=read();
b[i][2]=a[i].x2=read();
b[i][3]=a[i].y2=read();
}
solve(n);
for(int i=1;i<=n;i++){
if(s[i].count()!=2){
for(int j=0;j<4;j++)swap(b[i][j],b[n][j]);
n--;i--;
}
}
solve(n);
int ans=0;
for(int i=1;i<=n;i++){
if(s[i].count()==2)ans++;
}
write(ans/2);puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5916kb
input:
3 0 0 3 3 2 2 4 4 5 8 8 12
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 6036kb
input:
100 923310 372242 983605 907038 478627 492039 803226 736310 739241 381263 902708 567562 880442 960239 931687 994497 488788 247833 753798 332045 409430 647897 485436 789226 710160 614075 850921 635725 374903 876893 928920 992955 513455 801995 638877 931475 526983 755886 690371 898669 730825 514053 99...
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 6048kb
input:
100 668829 645577 739240 720922 827728 798471 840133 921016 166981 838674 177697 953637 607562 915466 744100 946011 461595 814141 601422 934072 531131 631369 575749 677973 966788 387713 969085 398515 48155 699081 115993 762903 121662 168194 237366 236805 870992 538874 982334 607408 640220 607061 766...
output:
0
result:
wrong answer 1st numbers differ - expected: '4', found: '0'