QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #420991 | #8672. 排队 | yswn# | 0 | 505ms | 444668kb | C++14 | 1.1kb | 2024-05-25 09:09:46 | 2024-05-25 09:09:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAX=2e5+10,N=460;
int n,q,K,B,l[MAX],r[MAX],x,y,mn,w[N][MAX<<1],L,R;
inline int read(){
int x=0,f=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
inline int work(int x,int L,int R){
mn=1e9;
for(int i=L;i<=R;++i){
if(x<l[i]){
mn=min(l[i]-1-x,mn);continue;
}if(x<=r[i]) mn=min(r[i]-x,mn),++x;
}return x;
}
signed main(){
n=read();q=read();K=450;B=(n+K-1)/K;
for(int i=1;i<=n;++i) l[i]=read(),r[i]=read();
// cout<<work(0,2,3)<<endl;
for(int i=1;i<=B;++i){
L=(i-1)*K+1,R=min(i*K,n);
x=0;
while(x<L){
y=work(x,L,R);
for(int j=0;j<=mn;++j) w[i][x+j]=y;
x+=mn+1;
}
}while(q--){
x=0;L=read();R=read();
int a=(L+K-1)/K,b=(R+K-1)/K;
x=work(x,L,min(a*K,R));
if(a==b){
printf("%d\n",x);continue;
}for(int i=a+1;i<b;++i) x=w[i][x];
x=work(x,(b-1)*K+1,R);
printf("%d\n",x);
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Memory Limit Exceeded
Test #1:
score: 10
Accepted
time: 1ms
memory: 7860kb
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
Memory Limit Exceeded
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:
result:
Subtask #2:
score: 0
Memory Limit Exceeded
Test #12:
score: 0
Memory Limit Exceeded
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
Wrong Answer
Test #22:
score: 0
Wrong Answer
time: 505ms
memory: 350708kb
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:
588 320 463 386 392 317 525 312 521 521 365 563 471 513 504 512 395 593 397 488 483 410 377 452 523 335 430 438 479 582 366 607 343 416 519 330 460 311 467 555 502 372 406 609 428 517 478 382 489 413 555 429 375 432 612 389 427 343 397 517 469 405 410 520 601 449 420 489 322 548 475 611 335 432 548 ...
result:
wrong answer 1st numbers differ - expected: '19141', found: '588'
Subtask #4:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 242ms
memory: 444668kb
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:
746 822 864 848 776 596 664 538 831 868 671 831 892 691 648 464 518 849 657 556 684 901 490 456 877 471 893 468 521 718 716 723 530 477 751 857 695 625 457 782 468 667 798 811 706 899 865 858 601 885 615 744 555 456 646 794 766 722 870 732 804 610 894 571 486 732 495 656 702 487 900 728 707 795 524 ...
result:
wrong answer 1st numbers differ - expected: '71224', found: '746'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%