QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#126557 | #4193. Joined Sessions | zhicheng | WA | 77ms | 9036kb | C++14 | 2.0kb | 2023-07-18 17:08:08 | 2023-07-18 17:08:10 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int p[200010],las[100010],con[100010],s[400010],dp[100010][4];
struct s{
int l,r;
bool operator<(s a){
if(l!=a.l){
return l<a.l;
}
return r<a.r;
}
}a[100010];
int m(int x,int y,int p){
if(p==1){
return max(x,y);
}
return min(x,y);
}
void update(int x,int y,int l,int r,int rt,int w){
int mid=(l+r)>>1;
if(l==r){
s[rt]=m(s[rt],y,w);
return;
}
if(x<=mid){
update(x,y,l,mid,rt<<1,w);
}
else{
update(x,y,mid+1,r,rt<<1|1,w);
}
s[rt]=m(s[rt<<1],s[rt<<1|1],w);
}
int query(int x,int y,int l,int r,int rt,int w){
int mid=(l+r)>>1,ans=w?0:1e9;
if(x<=l&&y>=r){
return s[rt];
}
if(x<=mid){
ans=m(ans,query(x,y,l,mid,rt<<1,w),w);
}
if(y>=mid+1){
ans=m(ans,query(x,y,mid+1,r,rt<<1|1,w),w);
}
return ans;
}
int main(){
int n,w=0,tot=0,pos;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].l,&a[i].r);
p[++tot]=a[i].l;
p[++tot]=a[i].r;
}
sort(a+1,a+n+1);
for(int i=2;i<=n;i++){
if(a[i].l<=a[i-1].r){
w=1;
break;
}
}
if(!w){
printf("impossible");
return 0;
}
sort(p+1,p+tot+1);
tot=unique(p+1,p+tot+1)-p-1;
for(int i=1;i<=n;i++){
a[i].l=lower_bound(p+1,p+tot+1,a[i].l)-p;
a[i].r=lower_bound(p+1,p+tot+1,a[i].r)-p;
}
for(int i=1;i<=n;i++){
if(a[i].l!=1){
las[i]=query(1,a[i].l-1,1,tot,1,1);
}
update(a[i].r,i,1,tot,1,1);
}
for(int i=1;i<=4*tot;i++){
s[i]=n+1;
}
for(int i=1;i<=n;i++){
con[i]=query(a[i].l,tot,1,tot,1,0);
update(a[i].r,i,1,tot,1,0);
if(con[i]==n+1){
con[i]=i;
}
}
memset(dp,127,sizeof(dp));
for(int j=0;j<=3;j++){
for(int i=1;i<=n;i++){
if(!las[i]){
dp[i][j]=1;
}
else{
pos=i;
for(int k=0;k<=j;k++){
pos=con[pos];
if(!las[pos]){
dp[i][j]=1;
break;
}
dp[i][j]=min(dp[i][j],dp[las[pos]][j-k]+1);
}
}
}
}
for(int i=1;i<=3;i++){
if(dp[n][i]<dp[n][0]){
printf("%d",i);
return 0;
}
}
printf("impossible");
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5148kb
input:
4 1 3 2 5 4 7 6 9
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7228kb
input:
5 1 3 4 7 8 10 2 5 6 9
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 2ms
memory: 5244kb
input:
3 1 2 2 3 3 4
output:
impossible
result:
ok single line: 'impossible'
Test #4:
score: 0
Accepted
time: 1ms
memory: 6004kb
input:
6 1 3 2 5 4 7 6 9 8 11 10 12
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 2ms
memory: 7268kb
input:
8 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9
output:
2
result:
ok single line: '2'
Test #6:
score: 0
Accepted
time: 2ms
memory: 7192kb
input:
5 1 2 2 3 3 4 5 6 6 7
output:
impossible
result:
ok single line: 'impossible'
Test #7:
score: 0
Accepted
time: 1ms
memory: 5588kb
input:
2 1 2 5 6
output:
impossible
result:
ok single line: 'impossible'
Test #8:
score: 0
Accepted
time: 0ms
memory: 7280kb
input:
2 1 3 2 4
output:
impossible
result:
ok single line: 'impossible'
Test #9:
score: 0
Accepted
time: 2ms
memory: 7216kb
input:
5 3 5 2 7 1 10 6 8 9 11
output:
impossible
result:
ok single line: 'impossible'
Test #10:
score: 0
Accepted
time: 0ms
memory: 7444kb
input:
10 229 315 444 459 459 828 232 324 350 371 208 235 371 430 430 456 324 350 172 208
output:
3
result:
ok single line: '3'
Test #11:
score: 0
Accepted
time: 0ms
memory: 7404kb
input:
15 227 313 471 486 487 522 230 322 377 398 206 233 398 457 457 483 322 348 102 138 138 206 348 377 476 506 522 885 67 102
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 1ms
memory: 5792kb
input:
20 261 347 505 520 521 556 264 356 411 432 240 267 432 491 491 517 356 382 136 172 172 240 382 411 510 540 556 579 67 102 579 931 22 80 69 136 271 327 11 53
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 2ms
memory: 5272kb
input:
50 383 469 703 718 719 754 386 478 584 605 362 389 619 678 689 715 498 524 172 208 211 279 524 553 708 738 788 811 67 102 855 857 22 80 69 136 393 449 11 53 229 302 421 440 710 747 198 222 315 385 413 439 91 171 882 1029 788 858 922 1077 305 330 84 111 336 341 772 801 313 370 124 219 539 584 740 807...
output:
1
result:
ok single line: '1'
Test #14:
score: 0
Accepted
time: 2ms
memory: 7216kb
input:
100 383 469 777 792 793 828 386 478 649 670 362 389 690 749 763 789 540 566 172 208 211 279 567 596 782 812 862 885 67 102 929 931 22 80 69 136 393 449 11 53 229 302 421 440 784 821 198 222 315 385 413 439 91 171 956 1029 862 932 996 1077 305 330 84 111 336 341 846 875 313 370 124 219 582 627 814 88...
output:
1
result:
ok single line: '1'
Test #15:
score: 0
Accepted
time: 2ms
memory: 7356kb
input:
500 383 469 777 792 793 828 386 478 649 670 362 389 690 749 763 789 540 566 172 208 211 279 567 596 782 812 862 885 67 102 929 931 22 80 69 136 393 449 11 53 229 302 421 440 784 821 198 222 315 385 413 439 91 171 956 1029 862 932 996 1077 305 330 84 111 336 341 846 875 313 370 124 219 582 627 814 88...
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 3ms
memory: 7532kb
input:
9999 383 469 777 792 793 828 386 478 649 670 362 389 690 749 763 789 540 566 172 208 211 279 567 596 782 812 862 885 67 102 929 931 22 80 69 136 393 449 11 53 229 302 421 440 784 821 198 222 315 385 413 439 91 171 956 1029 862 932 996 1077 305 330 84 111 336 341 846 875 313 370 124 219 582 627 814 8...
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 47ms
memory: 7592kb
input:
99998 383 469 777 792 793 828 386 478 649 670 362 389 690 749 763 789 540 566 172 208 211 279 567 596 782 812 862 885 67 102 929 931 22 80 69 136 393 449 11 53 229 302 421 440 784 821 198 222 315 385 413 439 91 171 956 1029 862 932 996 1077 305 330 84 111 336 341 846 875 313 370 124 219 582 627 814 ...
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 39ms
memory: 7752kb
input:
99999 383 469 777 792 793 828 386 478 649 670 362 389 690 749 763 789 540 566 172 208 211 279 567 596 782 812 862 885 67 102 929 931 22 80 69 136 393 449 11 53 229 302 421 440 784 821 198 222 315 385 413 439 91 171 956 1029 862 932 996 1077 305 330 84 111 336 341 846 875 313 370 124 219 582 627 814 ...
output:
1
result:
ok single line: '1'
Test #19:
score: 0
Accepted
time: 0ms
memory: 7208kb
input:
11 383 469 777 792 793 828 386 478 649 670 362 389 690 749 763 789 540 566 172 208 211 279
output:
impossible
result:
ok single line: 'impossible'
Test #20:
score: 0
Accepted
time: 2ms
memory: 5156kb
input:
16 383 469 777 792 793 828 386 478 649 670 362 389 690 749 763 789 540 566 172 208 211 279 567 596 782 812 862 885 67 102 929 931
output:
impossible
result:
ok single line: 'impossible'
Test #21:
score: 0
Accepted
time: 2ms
memory: 5900kb
input:
21 383 469 777 792 793 828 386 478 649 670 362 389 690 749 763 789 540 566 172 208 211 279 567 596 782 812 862 885 67 102 929 931 22 80 69 136 393 449 11 53 229 302
output:
impossible
result:
ok single line: 'impossible'
Test #22:
score: 0
Accepted
time: 1ms
memory: 7308kb
input:
51 766 852 1554 1569 1586 1621 772 864 1298 1319 724 751 1380 1439 1526 1552 1080 1106 344 380 422 490 1134 1163 1564 1594 1724 1747 134 169 1858 1860 44 102 138 205 786 842 22 64 458 531 842 861 1568 1605 396 420 630 700 826 852 182 262 1912 1985 1724 1794 1992 2073 610 635 168 195 672 677 1692 172...
output:
1
result:
ok single line: '1'
Test #23:
score: 0
Accepted
time: 2ms
memory: 7236kb
input:
110 766 852 1554 1569 1586 1621 772 864 1298 1319 724 751 1380 1439 1526 1552 1080 1106 344 380 422 490 1134 1163 1564 1594 1724 1747 134 169 1858 1860 44 102 138 205 786 842 22 64 458 531 842 861 1568 1605 396 420 630 700 826 852 182 262 1912 1985 1724 1794 1992 2073 610 635 168 195 672 677 1692 17...
output:
1
result:
ok single line: '1'
Test #24:
score: 0
Accepted
time: 2ms
memory: 7448kb
input:
501 766 852 1554 1569 1586 1621 772 864 1298 1319 724 751 1380 1439 1526 1552 1080 1106 344 380 422 490 1134 1163 1564 1594 1724 1747 134 169 1858 1860 44 102 138 205 786 842 22 64 458 531 842 861 1568 1605 396 420 630 700 826 852 182 262 1912 1985 1724 1794 1992 2073 610 635 168 195 672 677 1692 17...
output:
1
result:
ok single line: '1'
Test #25:
score: 0
Accepted
time: 7ms
memory: 5440kb
input:
9999 766 852 1554 1569 1586 1621 772 864 1298 1319 724 751 1380 1439 1526 1552 1080 1106 344 380 422 490 1134 1163 1564 1594 1724 1747 134 169 1858 1860 44 102 138 205 786 842 22 64 458 531 842 861 1568 1605 396 420 630 700 826 852 182 262 1912 1985 1724 1794 1992 2073 610 635 168 195 672 677 1692 1...
output:
1
result:
ok single line: '1'
Test #26:
score: 0
Accepted
time: 46ms
memory: 8600kb
input:
99998 766 852 1554 1569 1586 1621 772 864 1298 1319 724 751 1380 1439 1526 1552 1080 1106 344 380 422 490 1134 1163 1564 1594 1724 1747 134 169 1858 1860 44 102 138 205 786 842 22 64 458 531 842 861 1568 1605 396 420 630 700 826 852 182 262 1912 1985 1724 1794 1992 2073 610 635 168 195 672 677 1692 ...
output:
1
result:
ok single line: '1'
Test #27:
score: 0
Accepted
time: 45ms
memory: 8632kb
input:
99999 766 852 1554 1569 1586 1621 772 864 1298 1319 724 751 1380 1439 1526 1552 1080 1106 344 380 422 490 1134 1163 1564 1594 1724 1747 134 169 1858 1860 44 102 138 205 786 842 22 64 458 531 842 861 1568 1605 396 420 630 700 826 852 182 262 1912 1985 1724 1794 1992 2073 610 635 168 195 672 677 1692 ...
output:
1
result:
ok single line: '1'
Test #28:
score: 0
Accepted
time: 49ms
memory: 8596kb
input:
99998 3830 3916 7770 7785 7930 7965 3860 3952 6490 6511 3620 3647 6900 6959 7630 7656 5400 5426 1720 1756 2110 2178 5670 5699 7820 7850 8620 8643 670 705 9290 9292 220 278 690 757 3930 3986 110 152 2290 2363 4210 4229 7840 7877 1980 2004 3150 3220 4130 4156 910 990 9560 9633 8620 8690 9960 10041 305...
output:
2
result:
ok single line: '2'
Test #29:
score: 0
Accepted
time: 47ms
memory: 7716kb
input:
99999 3830 3916 7770 7785 7930 7965 3860 3952 6490 6511 3620 3647 6900 6959 7630 7656 5400 5426 1720 1756 2110 2178 5670 5699 7820 7850 8620 8643 670 705 9290 9292 220 278 690 757 3930 3986 110 152 2290 2363 4210 4229 7840 7877 1980 2004 3150 3220 4130 4156 910 990 9560 9633 8620 8690 9960 10041 305...
output:
2
result:
ok single line: '2'
Test #30:
score: 0
Accepted
time: 55ms
memory: 8468kb
input:
99998 38300 38386 77700 77715 79300 79335 38600 38692 64900 64921 36200 36227 69000 69059 76300 76326 54000 54026 17200 17236 21100 21168 56700 56729 78200 78230 86200 86223 6700 6735 92900 92902 2200 2258 6900 6967 39300 39356 1100 1142 22900 22973 42100 42119 78400 78437 19800 19824 31500 31570 41...
output:
impossible
result:
ok single line: 'impossible'
Test #31:
score: 0
Accepted
time: 60ms
memory: 8564kb
input:
99999 38300 38386 77700 77715 79300 79335 38600 38692 64900 64921 36200 36227 69000 69059 76300 76326 54000 54026 17200 17236 21100 21168 56700 56729 78200 78230 86200 86223 6700 6735 92900 92902 2200 2258 6900 6967 39300 39356 1100 1142 22900 22973 42100 42119 78400 78437 19800 19824 31500 31570 41...
output:
impossible
result:
ok single line: 'impossible'
Test #32:
score: 0
Accepted
time: 57ms
memory: 9032kb
input:
99999 383000 383086 777000 777015 793000 793035 386000 386092 649000 649021 362000 362027 690000 690059 763000 763026 540000 540026 172000 172036 211000 211068 567000 567029 782000 782030 862000 862023 67000 67035 929000 929002 22000 22058 69000 69067 393000 393056 11000 11042 229000 229073 421000 4...
output:
impossible
result:
ok single line: 'impossible'
Test #33:
score: -100
Wrong Answer
time: 77ms
memory: 9036kb
input:
99999 105683616 105692651 18111183 18114306 227651066 227657778 841261986 841276865 186689275 186699114 920321111 920342987 696518226 696523266 329159419 329169520 657138825 657162765 215002000 215018692 20317046 20329211 450700082 450717450 626431634 626445442 871848028 871877725 729687583 72969276...
output:
impossible
result:
wrong answer 1st lines differ - expected: '3', found: 'impossible'