QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#558351#8672. 排队djh03140 0ms0kbC++141.6kb2024-09-11 15:39:212024-09-11 15:39:25

Judging History

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

  • [2024-09-11 15:39:25]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-09-11 15:39:21]
  • 提交

answer

#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N = 1e6+5;
inline int read() {
	int x;
	scanf("%d",&x);
	return x;
}
int n, m,L[N],R[N];
struct Ques {
	int l,r,id;
	friend bool operator < (Ques a,Ques b) {
		return a.r<b.r;
	}
} qu[N];
int ans[N];
struct Tree {
	#define ls p<<1
	#define rs p<<1|1
	int c[N<<2],tag[N<<2];
	inline void pushup(int p) {
		c[p]=min(c[ls],c[rs]);
	}
	
	inline void cl(int p,int x) {
		c[p]+=x,tag[p]+=x;
	}
	
	inline void pushdown(int p) {
		cl(ls,tag[p]),cl(rs,tag[p]);
		tag[p]=0;
	}
	
	inline void change(int p,int L,int R,int l,int r) {
		if(l<=L && R<=r) return cl(p,1);
		pushdown(p);
		int mid=L+R>>1;
		if(l<=mid) change(ls,L,mid,l,r);
		if(mid<r)  change(rs,mid+1,R,l,r);
		pushup(p);
	}
	
	inline int query(int p,int L,int R,int x) {
		if(L==R) return c[p];
		int mid=L+R>>1;
		pushdown(p);
		if(x<=mid) return query(ls,L,mid,x);
		else return query(rs,mid+1,R,x);
	}
	
	inline int find(int p,int L,int R,int x) {
		if(L==R) return L;
		pushdown(p);
		int mid=L+R>>1;
		if(c[ls]<=x) return find(ls,L,mid,x);
		else find(rs,mid+1,R,x);
	}
} tr;
signed main() {
	n=read(),m=read();
	for(int i=1; i<=n; ++i) L[i]=read(),R[i]=read();
	for(int i=1; i<=m; ++i) qu[i].l=read(),qu[i].r=read(),qu[i].id=i;
	sort(qu+1,qu+m+1);
	int now=1;
	for(int i=1; i<=n; ++i) {
		int Lf=tr.find(1,1,n,R[i]),Rt=L[i]?(tr.find(1,1,n,L[i]-1)-1):i;
		Lf=max(Lf,1),Rt=min(Rt,i);
		if(Lf<=Rt) tr.change(1,1,n,Lf,Rt);
		while(now<=m && qu[now].r<=i) ans[qu[now].id]=tr.query(1,1,n,qu[now].l),++now;
	}
	for(int i=1; i<=m; ++i) cout<<ans[i]<<"\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

input:

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

output:


result:


Subtask #2:

score: 0
Runtime Error

Test #12:

score: 0
Runtime Error

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:


result:


Subtask #3:

score: 0
Runtime Error

Test #22:

score: 0
Runtime Error

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:


result:


Subtask #4:

score: 0
Runtime Error

Test #32:

score: 0
Runtime Error

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:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%