QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#33721#4219. InsectsQingyuWA 3ms9952kbC++232.9kb2022-06-04 18:22:242022-06-04 18:22:24

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:22:24]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:9952kb
  • [2022-06-04 18:22:24]
  • 提交

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(){
	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: 100
Accepted
time: 3ms
memory: 7860kb

input:

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

output:

1
2
2
3

result:

ok 4 number(s): "1 2 2 3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 7868kb

input:

9
22 44
7 6
10 48
46 20
21 35
33 16
36 41
29 4
45 22
7
46 39
44 32
1 48
43 19
28 34
8 48
15 18

output:

1
2
2
3
4
4
4

result:

ok 7 numbers

Test #3:

score: 0
Accepted
time: 3ms
memory: 7780kb

input:

7
25 13
38 45
30 28
28 29
16 34
45 4
47 13
8
24 16
10 18
8 28
40 47
28 35
5 25
29 0
41 17

output:

0
0
0
1
2
2
2
3

result:

ok 8 numbers

Test #4:

score: 0
Accepted
time: 3ms
memory: 9700kb

input:

10
47 32
0 16
18 11
17 19
40 49
36 24
3 26
15 45
23 29
42 3
5
42 18
22 3
30 13
35 19
43 29

output:

1
1
2
3
4

result:

ok 5 number(s): "1 1 2 3 4"

Test #5:

score: 0
Accepted
time: 3ms
memory: 9952kb

input:

6
2 5
22 3
28 41
41 36
9 8
8 17
2
24 7
49 35

output:

1
2

result:

ok 2 number(s): "1 2"

Test #6:

score: 0
Accepted
time: 0ms
memory: 9832kb

input:

2
27 36
5 39
6
47 22
45 4
44 2
24 2
29 11
21 37

output:

0
0
0
0
0
0

result:

ok 6 numbers

Test #7:

score: -100
Wrong Answer
time: 3ms
memory: 7800kb

input:

30
35 14
26 38
50 17
21 0
14 0
39 2
5 45
1 18
22 50
5 49
35 16
37 43
15 11
22 16
4 9
44 36
1 23
42 19
33 44
2 44
35 16
21 36
23 46
39 1
15 29
9 17
31 27
37 50
15 24
30 38
48
10 38
28 0
33 5
33 11
36 27
4 30
4 18
23 28
4 8
16 20
24 47
14 34
30 45
47 10
4 48
36 2
10 20
11 39
49 39
11 50
48 36
28 41
23...

output:

1
2
3
4
5
6
7
8
8
9
10
10
11
12
13
13
13
13
14
15
16
17
17
17
18
18
19
20
21
22
22
22
22
22
22
22
23
23
23
23
24
24
24
25
26
26
26
26

result:

wrong answer 31st numbers differ - expected: '23', found: '22'