QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#644341#4671. Independent RectanglescjxWA 1ms6048kbC++202.0kb2024-10-16 13:24:122024-10-16 13:24:12

Judging History

你现在查看的是最新测评结果

  • [2024-10-16 13:24:12]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6048kb
  • [2024-10-16 13:24:12]
  • 提交

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'