QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#558524#8672. 排队Idtwtei0 107ms31872kbC++201.9kb2024-09-11 16:36:102024-09-11 16:36:11

Judging History

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

  • [2024-09-11 16:36:11]
  • 评测
  • 测评结果:0
  • 用时:107ms
  • 内存:31872kb
  • [2024-09-11 16:36:10]
  • 提交

answer

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

#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
const int N=1e6+100,INF=1e9;
#define gc getchar()
#define rd read()
inline int read(){
	int x=0,f=0; char c=gc;
	for(;c<'0'||c>'9';c=gc) f|=(c=='-');
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

int n,m,ans[N],x[N],y[N];
vector<pii> q[N];

#define lc (id<<1)
#define rc (id<<1|1)
#define mid (l+r>>1)
struct TREE{ int mn,mx,atag; }t[N<<2];
void pushup(int id){ t[id].mn=t[lc].mn,t[id].mx=t[rc].mx; }
void add0(int id,int v){ t[id].mn+=v,t[id].mx+=v,t[id].atag+=v; }
void spread(int id){ int &v=t[id].atag; if(v!=0) add0(lc,v),add0(rc,v),v=0; }
void bui(int id,int l,int r){
	t[id]={INF,-INF,0}; if(l==r) return;
	bui(lc,l,mid),bui(rc,mid+1,r);
}
void chg(int id,int l,int r,int ql,int v){
	if(l==r) return t[id].mn=t[id].mx=v,void(); spread(id);
	ql<=mid?chg(lc,l,mid,ql,v):chg(rc,mid+1,r,ql,v); pushup(id);
}
void add(int id,int l,int r,int ql,int qr,int v){
	if(ql<=l&&r<=qr) return add0(id,v); spread(id);
	if(ql<=mid) add(lc,l,mid,ql,qr,v);
	if(qr>=mid+1) add(rc,mid+1,r,ql,qr,v);
	pushup(id);
}
int ask(int id,int l,int r,int ql){
	if(l==r) return t[id].mn; spread(id);
	return ql<=mid?ask(lc,l,mid,ql):ask(rc,mid+1,r,ql);
}
int ask0(int id,int l,int r,int v){
	if(l==r) return l; spread(id);
	return t[rc].mx>=v?ask0(rc,mid+1,r,v):ask0(lc,l,mid,v);
}
int ask1(int id,int l,int r,int v){
	if(l==r) return l; spread(id);
	return t[lc].mn<=v?ask1(lc,l,mid,v):ask1(rc,mid+1,r,v);	
}
#undef lc
#undef rc
#undef mid

int main(){
	
	n=rd,m=rd;
	for(int i=1;i<=n;++i) x[i]=rd,y[i]=rd;
	for(int i=1,l,r;i<=m;++i) l=rd,r=rd,q[r].pb({l,i});
	
	bui(1,1,n);
	for(int i=1;i<=n;++i){
		chg(1,1,n,i,0),add(1,1,n,ask1(1,1,n,y[i]),ask0(1,1,n,x[i]),1);
		for(auto [l,id]:q[i]) ans[id]=ask(1,1,n,l);
	}
	for(int i=1;i<=m;++i) printf("%d\n", ans[i]);
	
	return 0;
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 0ms
memory: 9900kb

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: 0
Wrong Answer
time: 0ms
memory: 10384kb

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:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #12:

score: 0
Wrong Answer
time: 64ms
memory: 26892kb

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:

11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
11
...

result:

wrong answer 1957th numbers differ - expected: '1', found: '8'

Subtask #3:

score: 0
Wrong Answer

Test #22:

score: 0
Wrong Answer
time: 94ms
memory: 31872kb

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:

221
0
0
0
0
0
21001
90509
0
76000
62999
49734
2505
0
0
31396
35181
45576
60911
42579
0
0
0
0
41333
0
0
12463
44559
104227
0
0
0
31300
7988
71186
0
22498
49348
45836
3776
15095
17598
59606
13654
39523
88574
4840
0
0
87210
0
104020
43416
59916
0
82073
19073
0
0
1015
4863
42843
0
65318
51605
29491
1913...

result:

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

Subtask #4:

score: 0
Wrong Answer

Test #32:

score: 0
Wrong Answer
time: 107ms
memory: 24924kb

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:

55146
0
44864
0
28126
27646
144614
126489
157628
71418
22018
96129
87243
5838
70298
0
46615
0
0
64806
45584
35449
0
0
0
13869
111544
50318
636
0
0
170570
48580
50378
0
90806
116294
75
0
0
0
0
0
106308
0
0
57013
71858
122747
3485
67616
0
119305
24257
26043
0
40714
0
29570
0
704
0
56594
62120
0
0
0
50...

result:

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

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%