QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#558524 | #8672. 排队 | Idtwtei | 0 | 107ms | 31872kb | C++20 | 1.9kb | 2024-09-11 16:36:10 | 2024-09-11 16:36:11 |
Judging History
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%