QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#412950#8672. 排队g1ove0 363ms71304kbC++141.9kb2024-05-16 22:06:252024-05-16 22:06:26

Judging History

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

  • [2024-05-16 22:06:26]
  • 评测
  • 测评结果:0
  • 用时:363ms
  • 内存:71304kb
  • [2024-05-16 22:06:25]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
const int inf=1e9+5;
int n,m;
int l[N],r[N];
int stk[N],top;
struct segtree{
	int tr[N*4],lz[N*4],p[N*4];
	void Pushup(int x)
	{
		if(tr[x*2]<=0) tr[x]=tr[x*2],p[x]=p[x*2];
		else tr[x]=tr[x*2+1],p[x]=p[x*2+1];
	} 
	void Pushdown(int x)
	{
		if(!lz[x]) return;
		tr[x*2]+=lz[x];
		tr[x*2+1]+=lz[x];
		lz[x*2]+=lz[x];
		lz[x*2+1]+=lz[x];
		lz[x]=0;
	}
	void modify(int l,int r,int L,int R,int x,int v)
	{
		if(l>R||r<L) return;
		if(l>=L&&r<=R)
		{
			tr[x]+=v;
			lz[x]+=v;
			if(l==r) p[x]=l;
			return;
		}
		int mid=(l+r)/2;
		Pushdown(x);
		modify(l,mid,L,R,x*2,v);
		modify(mid+1,r,L,R,x*2+1,v);
		Pushup(x);
	}
	int query(int l,int r,int p,int x)
	{
		if(l==r) return tr[x];
		int mid=(l+r)/2;
		Pushdown(x);
		if(p<=mid) return query(l,mid,p,x*2);
		else return query(mid+1,r,p,x*2+1);
	}
}tr1,tr2,tr3;
int ans[N];
struct node{
	int p,id;
};
vector<node> E[N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&l[i],&r[i]),
		tr1.modify(1,n,i,i,1,inf),
		tr2.modify(1,n,i,i,1,inf);
	for(int i=1;i<=m;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		E[l].push_back((node){r,i});
	}
	for(int i=n;i>=1;i--)
	{
		tr1.modify(1,n,i,i,1,l[i]-inf);
		tr2.modify(1,n,i,i,1,r[i]+1-inf);
		while(1)
		{
			int l1=tr1.p[1],l2=tr2.p[1];
			if(tr1.tr[1]>0&&tr2.tr[1]>0) break;
			if(tr1.tr[1]>0) l1=inf;
			if(tr2.tr[1]>0) l2=inf;
			if(l1<l2)
			{
				tr1.modify(1,n,l1,l1,1,inf);
				tr1.modify(1,n,l1+1,n,1,-1);
				tr2.modify(1,n,l1+1,n,1,-1);
				tr3.modify(1,n,l1,n,1,1);
			}
			else
			{
				tr2.modify(1,n,l2,l2,1,inf);
				tr1.modify(1,n,l2+1,n,1,1);
				tr2.modify(1,n,l2+1,n,1,1);
				tr3.modify(1,n,l2,n,1,-1);
			}
		}
		for(auto u:E[i]) ans[u.id]=tr3.query(1,n,u.p,1);
	}
	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: 10
Accepted
time: 3ms
memory: 44196kb

input:

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

output:

1
3
1

result:

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

Test #2:

score: -10
Wrong Answer
time: 8ms
memory: 45296kb

input:

5000 5000
5 10
3 9
3 8
2 7
2 5
3 6
1 5
0 2
7 8
2 10
0 3
3 6
4 6
1 6
4 8
7 8
2 7
3 4
4 9
7 8
2 9
2 5
3 6
0 5
6 7
1 2
2 4
2 10
1 5
7 9
6 9
2 3
9 10
5 5
2 9
3 3
2 7
2 4
0 6
0 3
1 7
7 7
4 8
2 9
4 8
0 10
1 8
1 1
2 7
5 9
1 7
1 7
1 4
2 4
1 4
2 9
1 7
4 7
3 8
1 3
4 6
1 5
1 6
0 0
3 9
4 7
2 8
1 8
1 2
7 8
2 7
2...

output:

316
109
875
260
52
825
1362
1219
193
65
204
161
1507
165
505
374
756
854
1051
660
480
58
682
920
140
497
21
21
680
1275
1310
244
628
229
401
870
15
366
1116
392
53
1005
337
781
973
24
999
340
558
459
301
237
458
375
338
902
460
106
725
339
894
1031
411
418
699
1153
677
754
905
613
46
732
565
722
726...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #12:

score: 0
Wrong Answer
time: 238ms
memory: 65500kb

input:

200000 200000
3 6
3 3
6 10
1 7
2 7
6 9
4 6
3 4
0 8
0 6
3 5
3 4
1 8
7 8
4 5
0 3
1 5
2 9
1 2
1 2
3 4
5 7
6 10
3 9
4 7
1 6
2 6
1 7
2 5
1 7
6 8
1 1
0 7
7 8
0 9
1 7
3 8
3 7
1 2
4 8
5 6
0 6
5 6
2 7
2 6
0 6
0 6
1 7
2 5
0 3
0 3
7 10
3 8
0 2
3 4
3 7
4 9
0 6
4 7
2 6
8 10
2 10
4 10
3 3
2 6
4 5
3 9
1 8
1 2
2 9
...

output:

47280
56522
45423
9639
12949
1423
51335
31714
52156
25463
64894
33224
4934
50146
65911
54609
6068
29679
24017
15224
3369
13400
15278
43780
1717
2778
35607
33387
22383
21666
23362
33345
46769
34391
14125
56772
55523
28810
64343
37752
40033
25497
25993
47075
647
29761
65142
48211
12855
12276
18188
331...

result:

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

Subtask #3:

score: 0
Wrong Answer

Test #22:

score: 0
Wrong Answer
time: 363ms
memory: 71304kb

input:

200000 200000
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 0
0 9
0 10
0 0
0 0
0 13
0 14
0 0
0 16
0 17
0 18
0 19
0 0
0 21
0 22
0 23
0 0
0 0
0 0
0 0
0 28
0 0
0 30
0 31
0 32
0 33
0 34
0 35
0 0
0 0
0 38
0 39
0 40
0 41
0 42
0 43
0 44
0 45
0 46
0 0
0 48
0 49
0 50
0 51
0 52
0 53
0 54
0 55
0 56
0 57
0 0
0 59
0 60
0 0
0 0
...

output:

22432
46052
17444
68789
18109
5870
30967
109395
3294
91576
75155
65043
3007
17824
29172
67569
42104
60169
79239
52762
32527
29078
63908
31551
85805
8848
4540
48908
79576
122635
51073
4419
15232
37151
20241
100118
19478
33634
75043
66160
27978
56059
26747
100983
44152
52519
104178
42562
18576
39534
1...

result:

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

Subtask #4:

score: 0
Wrong Answer

Test #32:

score: 0
Wrong Answer
time: 310ms
memory: 69764kb

input:

200000 200000
0 200000
1 200000
1 200000
0 200000
0 200000
1 200000
1 200000
1 200000
0 200000
1 200000
0 200000
0 200000
1 200000
0 200000
0 200000
0 200000
0 200000
1 200000
0 200000
0 200000
1 200000
0 200000
1 200000
1 200000
1 200000
1 200000
0 200000
0 200000
1 200000
2 200000
1 200000
2 20000...

output:

54636
16364
50225
36116
47652
22447
111995
104549
126674
62368
19447
92053
80388
9653
69469
24435
38547
11858
1171
81264
70550
54701
12887
3741
29193
26623
102060
75549
515
20084
5042
132989
46796
54961
12052
85968
96225
11666
31965
23363
18421
13285
8448
88323
17067
28729
77724
91867
96842
36159
53...

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%