QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#126021 | #4193. Joined Sessions | zjy0001 | AC ✓ | 58ms | 13692kb | C++17 | 2.3kb | 2023-07-18 09:08:12 | 2023-07-18 09:08:18 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define ldb long double
using namespace std;
typedef pair<int,int> PII;
#define gc() getchar()
#define pc(x) putchar(x)
template<class T>inline T read(){
T x=0;char ch;bool f=1;
while(!isdigit(ch=gc()))if(ch=='-')f^=1;
do x=(x<<1)+(x<<3)+(ch^48);while(isdigit(ch=gc()));
return f?x:-x;
}
#define read() read<int>()
const int N=1e5+5,Mod=998244353;
int n,m,flg;
PII A[N];
int f[4][N];
int pre[N],nxt[N],B[N<<1],F[N<<3],G[N<<3];
void build(int p,int l,int r){
F[p]=n+1,G[p]=0;
if(l==r)return;
int mid=(l+r)>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
void updmin(int p,int l,int r,int x,int y){
F[p]=min(F[p],y);
if(l==r)return;
int mid=(l+r)>>1;
if(x<=mid)updmin(p<<1,l,mid,x,y);
else updmin(p<<1|1,mid+1,r,x,y);
}
void updmax(int p,int l,int r,int x,int y){
G[p]=max(G[p],y);
if(l==r)return;
int mid=(l+r)>>1;
if(x<=mid)updmax(p<<1,l,mid,x,y);
else updmax(p<<1|1,mid+1,r,x,y);
}
int qmin(int p,int l,int r,int x){
if(x<=l)return F[p];
int mid=(l+r)>>1;
if(x>mid)return qmin(p<<1|1,mid+1,r,x);
return min(qmin(p<<1,l,mid,x),F[p<<1|1]);
}
int qmax(int p,int l,int r,int x){
if(r<=x)return G[p];
int mid=(l+r)>>1;
if(x<=mid)return qmax(p<<1,l,mid,x);
return max(G[p<<1],qmax(p<<1|1,mid+1,r,x));
}
signed main(){
n=read();
for(int i=1;i<=n;++i){
int l=B[++m]=read(),r=B[++m]=read();
A[i]=PII(l,r);
}
sort(A+1,A+n+1),sort(B+1,B+m+1),m=unique(B+1,B+m+1)-B-1;
for(int i=2;i<=n;++i)if(A[i-1].second>=A[i].first)flg=1;
if(!flg)return puts("impossible"),0;
build(1,1,m);
for(int i=1;i<=n;++i){
A[i].first=lower_bound(B+1,B+m+1,A[i].first)-B;
A[i].second=lower_bound(B+1,B+m+1,A[i].second)-B;
if(A[i].first!=1)pre[i]=qmax(1,1,m,A[i].first-1);
updmax(1,1,m,A[i].second,i);
}
for(int i=1;i<=n;++i){
nxt[i]=qmin(1,1,m,A[i].first);
updmin(1,1,m,A[i].second,i);
if(nxt[i]==n+1)nxt[i]=i;
}
memset(f,0x3f,sizeof(f));
for(int j=0;j<=3;++j)for(int i=1;i<=n;++i)
if(!pre[i])f[j][i]=1;
else for(int k=0,p=i;k<=j;++k)
if(!pre[p=nxt[p]]){
f[j][i]=1;
break;
}
else f[j][i]=min(f[j][i],f[j-k][pre[p]]+1);
puts(f[1][n]<f[0][n]?"1":(f[2][n]<f[0][n]?"2":(f[3][n]<f[0][n]?"3":"impossible")));
return 0;
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9940kb
input:
4 1 3 2 5 4 7 6 9
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 2ms
memory: 9808kb
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: 9548kb
input:
3 1 2 2 3 3 4
output:
impossible
result:
ok single line: 'impossible'
Test #4:
score: 0
Accepted
time: 2ms
memory: 9644kb
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: 1ms
memory: 9636kb
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: 0ms
memory: 9544kb
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: 5384kb
input:
2 1 2 5 6
output:
impossible
result:
ok single line: 'impossible'
Test #8:
score: 0
Accepted
time: 2ms
memory: 9748kb
input:
2 1 3 2 4
output:
impossible
result:
ok single line: 'impossible'
Test #9:
score: 0
Accepted
time: 2ms
memory: 9632kb
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: 8788kb
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: 2ms
memory: 10424kb
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: 9932kb
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: 9640kb
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: 9552kb
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: 1ms
memory: 9832kb
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: 10532kb
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: 27ms
memory: 10396kb
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: 25ms
memory: 9548kb
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: 2ms
memory: 10276kb
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: 1ms
memory: 9728kb
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: 1ms
memory: 9548kb
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: 2ms
memory: 8696kb
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: 1ms
memory: 9540kb
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: 10480kb
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: 6ms
memory: 9876kb
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: 30ms
memory: 10220kb
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: 28ms
memory: 9608kb
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: 32ms
memory: 10608kb
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: 27ms
memory: 10844kb
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: 40ms
memory: 10168kb
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: 28ms
memory: 12488kb
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: 41ms
memory: 11568kb
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: 0
Accepted
time: 46ms
memory: 13532kb
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:
3
result:
ok single line: '3'
Test #34:
score: 0
Accepted
time: 48ms
memory: 13532kb
input:
99999 621671866 621689355 260637225 260671451 369704836 369710724 725685662 725710508 22428571 22443369 642856993 642885299 698285582 698312712 120410361 120429207 167592012 167604340 205374731 205394706 365617680 365643193 860995202 861000055 267302066 267326200 238978436 238990560 84846707 8485401...
output:
3
result:
ok single line: '3'
Test #35:
score: 0
Accepted
time: 52ms
memory: 13460kb
input:
99999 453457655 453479336 744967415 744983991 599539613 599552610 804296688 804307342 731746013 731888389 797264655 797287818 942438092 942462518 893112015 893173067 569467815 569471608 717411287 717431783 802785379 802841071 531883863 531911803 342147899 342185849 352838933 352859499 224245637 2242...
output:
3
result:
ok single line: '3'
Test #36:
score: 0
Accepted
time: 57ms
memory: 13556kb
input:
99999 175386704 175599566 358283198 358366127 18806211 19163132 394562342 394681629 925603355 926365928 40371148 40478709 523681777 524107404 226575947 226898929 356770293 356928466 600146546 600195586 586576969 586868047 521564139 521908893 324325487 324557830 68538995 68743149 24642808 24759034 65...
output:
3
result:
ok single line: '3'
Test #37:
score: 0
Accepted
time: 45ms
memory: 13660kb
input:
99999 898578216 898756004 118732762 119481878 450467503 451253718 497745704 498721863 871077176 871082620 999580163 999720990 695992163 696856126 887875007 888927751 329075031 330721148 843572572 845458018 732416852 733368564 741413694 743170711 972825337 973493710 851863955 852268984 77241841 77479...
output:
3
result:
ok single line: '3'
Test #38:
score: 0
Accepted
time: 45ms
memory: 13692kb
input:
99999 762130104 762133110 29274639 29283121 13583407 13597071 841205062 841216772 608178029 608184133 920248306 920256470 696459412 696479453 329061045 329068465 430361122 430367982 178535270 178544839 40471992 40480261 584659324 584674991 21259564 21268129 871786431 871797215 729544725 729562836 75...
output:
2
result:
ok single line: '2'
Test #39:
score: 0
Accepted
time: 47ms
memory: 13480kb
input:
99999 521888913 521896003 260045736 260057508 852458694 852483860 725300193 725333541 764288966 764299433 333323692 333364521 701246937 701262245 120295408 120316480 638996373 639001386 652473287 652496025 25181905 25198304 861499720 861511451 266569934 266578928 739253304 739257931 492628921 492632...
output:
2
result:
ok single line: '2'
Test #40:
score: 0
Accepted
time: 52ms
memory: 13564kb
input:
99999 768910257 768917146 181915531 181920034 888742035 888748385 889154491 889197238 228572265 228597707 796645822 796658078 930170035 930194099 96705376 96744528 378477215 378478533 548799115 548803550 21581826 21668101 809731226 809765896 590751433 590796004 388581259 388621259 349484847 34949962...
output:
2
result:
ok single line: '2'
Test #41:
score: 0
Accepted
time: 58ms
memory: 13556kb
input:
99999 960753627 960924552 33810416 33940954 557941636 558194321 120450159 120662984 353102680 353179426 826473779 826483990 548021159 548831641 906244211 906283169 917634317 918029956 996262722 996433740 101393639 101469847 694017817 694138160 148097305 148318573 215648548 216209741 441170019 441388...
output:
2
result:
ok single line: '2'
Test #42:
score: 0
Accepted
time: 54ms
memory: 13664kb
input:
99999 358545525 358853170 121272448 122048246 106053528 106420248 226385604 226408881 926236504 926383897 747664232 748184131 96744528 99358138 807709086 807727473 608689568 608783079 680942518 681885410 345770945 346914479 903696330 904244793 878041641 878197234 100923784 101561374 324419402 326645...
output:
2
result:
ok single line: '2'