QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#812093#62. Examinationguleng2007#0 140ms12352kbC++231.5kb2024-12-13 11:27:492024-12-13 11:27:51

Judging History

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

  • [2024-12-13 11:27:51]
  • 评测
  • 测评结果:0
  • 用时:140ms
  • 内存:12352kb
  • [2024-12-13 11:27:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+5;

struct node
{
	int a, b, c, op;
} q[N], a[N];

int c[N], ans[N], num[N], cnt;

bool cmp(node a,node b)
{
	if(a.a!=b.a)
		return a.a>b.a;
	if(a.b!=b.b)
		return a.b>b.b;
	if(a.c!=b.c)
		return a.c>b.c;
	return a.op<b.op;
}

void update(int x,int y)
{
	for(int i=x;i;i-=i&-i)
		c[i] += y;
}

int query(int x)
{
	int ans=0;
	for(int i=x;i<=cnt;i+=i&-i)
		ans += c[i];
	return ans;
}

void CDQ(int l,int r)
{
	if(l==r)
		return;

	int mid=(l+r)/2;
	CDQ(l,mid);
	CDQ(mid+1,r);

	int cur1=l, cur2=mid+1, cur=l;
	while(cur1<=mid || cur2<=r)
	{
		if(cur2>r || (cur1<=mid && q[cur1].b>=q[cur2].b))
		{
			if(q[cur1].op==0)
				update(q[cur1].c,1);
			a[cur++]=q[cur1++];
		}
		else
		{
			if(q[cur2].op)
				ans[q[cur2].op] += query(q[cur2].c);
			a[cur++]=q[cur2++];
		}
	}

	for(int i=l;i<=r;i++)
		q[i]=a[i];

	for(int i=l;i<=mid;i++)
		if(q[i].op==0)
			update(q[i].c,-1);
}

int main()
{
	int n, m;
	cin >> n >> m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&q[i].a,&q[i].b);
		q[i].c=q[i].a+q[i].b;
		q[i].op=0;
	}

	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&q[i+n].a,&q[i+n].b,&q[i+n].c);
		q[i+n].op=i;
	}

	for(int i=1;i<=n+m;i++)
		num[++cnt]=q[i].c;

	sort(num+1,num+cnt+1);
	cnt=unique(num+1,num+cnt+1)-num-1;

	for(int i=1;i<=n+m;i++)
		q[i].c=lower_bound(num+1,num+cnt+1,q[i].c)-num;
	
	sort(q+1,q+n+m+1,cmp);

	CDQ(1,n+m);

	for(int i=1;i<=m;i++)
		printf("%d\n",ans[i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 10020kb

input:

10 10
28 2
78 81
39 79
61 31
36 99
90 5
20 55
91 4
48 19
80 7
52 43 78
64 65 171
34 68 124
37 80 161
53 19 123
49 58 109
95 46 30
45 48 60
47 13 54
64 30 144

output:

-2
0
-8
0
-3
-5
0
-1
2
-3

result:

wrong answer 1st lines differ - expected: '1', found: '-2'

Subtask #2:

score: 0
Wrong Answer

Test #19:

score: 0
Wrong Answer
time: 140ms
memory: 12352kb

input:

100000 100000
26753 11234
32815 62591
34318 93262
77179 57605
88208 33327
48449 99060
42403 58561
85715 7001
2418 90938
77409 6957
546 83283
53957 8374
49470 1483
65866 64950
4269 8745
19041 85833
22344 90706
92926 35603
54697 75311
72601 66401
77598 8193
3751 54202
32710 5877
23835 38264
34381 3338...

output:

3653
15966
23790
15538
14595
27036
6072
30862
30067
25519
19361
10384
30042
217
18506
3524
1976
18295
39435
19228
69121
26191
13796
9127
18425
1135
13489
21335
16021
74125
30297
69775
45636
56523
1039
58483
8623
3333
3199
6308
9663
39612
40495
7959
42857
11111
26691
20517
75503
28392
4292
28300
6590...

result:

wrong answer 1st lines differ - expected: '3392', found: '3653'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%