QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#33724#4219. Insectshe_____heWA 4ms9864kbC++3.0kb2022-06-04 18:56:022022-06-04 18:56:04

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-04 18:56:04]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:9864kb
  • [2022-06-04 18:56:02]
  • 提交

answer

// xtqqwq
#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}

int readint(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,m,nx,ny,k;
int px[200005],py[200005],g[200005],del[200005],ans[100005];
pii a[100005],b[100005];
pair<pii,int> val[200005];

void add(int x,int y){
	for(;x<=m;x+=(x&(-x))) g[x]+=y;
}

int ask(int x){
	int ret=0;
	for(;x;x-=(x&(-x))) ret+=g[x];
	return ret;
}

void solve(int l,int r,vector<pair<pii,int> > &vec,int sum){
//	cout<<"######################### solve "<<l<<' '<<r<<' '<<sum<<endl;
//	for(auto r:vec) cout<<r.se<<' ';
//	cout<<endl;
	int mid=(l+r)/2;
	k=0;
	for(auto r:vec) if(r.se<=mid) val[++k]=r;
	sort(val+1,val+k+1,[&](pair<pii,int> x,pair<pii,int> y){return x.fi==y.fi?x.se>y.se:x.fi.fi==y.fi.fi?x.fi.se>y.fi.se:x.fi.fi<y.fi.fi;});
	multiset<int> st;
	int all=0;
	for(int i=1;i<=k;i++){
		if(val[i].se){
			auto it=st.upper_bound(val[i].fi.se);
			if(it!=st.begin()){
				it--;
				all++;
				del[i]=*it;
				st.erase(it);
			}
			else del[i]=0;
		}
		else st.insert(val[i].fi.se);
	}
//	cout<<"test "<<mid<<' '<<all<<' '<<ask(l)<<endl;
	if(l==r) return (void)(ans[l]=sum+all+ask(l));
	int pl=1,rval=0;
	vector<int> chn;
	vector<pair<pii,int> > lson,rson;
	for(int i=k;i>=1;i--){
		if(val[i].se){
			if(val[i].fi.se>=pl&&pl>=del[i]) pl=val[i].fi.se+1;
		}
		if(val[i].fi.se<pl){
			lson.pb(val[i]),rval+=val[i].se==0;
		}
		else{
			rson.pb(val[i]);
			if(val[i].se) chn.pb(val[i].se);
		}
//		cout<<pl<<' ';
	}
//	cout<<endl;
	for(auto r:vec) if(r.se>mid) rson.pb(r);
//	cout<<"lson "<<lson.size()<<' '<<rson.size()<<' '<<all<<endl;
	for(auto r:chn) add(r,1);
	solve(l,mid,lson,sum);
	for(auto r:chn) add(r,-1);
	solve(mid+1,r,rson,sum+rval);
}

int main(){
//	freopen("black.in","r",stdin);
//	freopen("black.out","w",stdout);
	n=readint();
	for(int i=1;i<=n;i++) px[++nx]=a[i].fi=readint(),py[++ny]=a[i].se=readint();
	m=readint();
	for(int i=1;i<=m;i++) px[++nx]=b[i].fi=readint(),py[++ny]=b[i].se=readint();
	sort(px+1,px+nx+1);
	nx=unique(px+1,px+nx+1)-px-1;
	sort(py+1,py+ny+1);
	ny=unique(py+1,py+ny+1)-py-1;
	for(int i=1;i<=n;i++){
		a[i].fi=lower_bound(px+1,px+nx+1,a[i].fi)-px;
		a[i].se=lower_bound(py+1,py+ny+1,a[i].se)-py;
	}
	for(int i=1;i<=m;i++){
		b[i].fi=lower_bound(px+1,px+nx+1,b[i].fi)-px;
		b[i].se=lower_bound(py+1,py+ny+1,b[i].se)-py;
	}
	vector<pair<pii,int> > vec;
	for(int i=1;i<=n;i++) vec.pb(mp(a[i],0));
	for(int i=1;i<=m;i++) vec.pb(mp(b[i],i));
	solve(1,m,vec,0);
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 9864kb

input:

3
0 0
1 1
2 2
4
0 0
1 1
0 0
3 3

output:

0
1
1
2

result:

wrong answer 1st numbers differ - expected: '1', found: '0'