QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#558351 | #8672. 排队 | djh0314 | 0 | 0ms | 0kb | C++14 | 1.6kb | 2024-09-11 15:39:21 | 2024-09-11 15:39:25 |
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%