QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#431298 | #4193. Joined Sessions | kevinyang# | WA | 197ms | 46512kb | C++14 | 4.0kb | 2024-06-05 10:52:31 | 2024-06-05 10:52:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
struct SegTree{
int size;
vector<pii>arr;
void init(int n){
size = 1;
while(size<n)size*=2;
arr.resize(2*size);
}
void set(int i, pii v, int x, int lx, int rx){
if(rx-lx==1){
arr[x] = v;
return;
}
int m = (lx+rx)/2;
if(i<m){
set(i,v,2*x+1,lx,m);
}
else{
set(i,v,2*x+2,m,rx);
}
arr[x] = min(arr[2*x+1],arr[2*x+2]);
}
void set(int i,pii v){
set(i,v,0,0,size);
}
pii query(int l,int r, int x, int lx, int rx){
if(lx>=r||l>=rx)return {(int)1e9+7,0LL};
if(lx>=l&&rx<=r)return arr[x];
int m = (lx+rx)/2;
pii s1 = query(l,r,2*x+1,lx,m);
pii s2 = query(l,r,2*x+2,m,rx);
return min(s1,s2);
}
pii query(int l, int r){
return query(l,r,0,0,size);
}
};
struct SegTree2{
int size;
vector<pii>arr;
void init(int n){
size = 1;
while(size<n)size*=2;
arr.resize(2*size);
}
void set(int i, pii v, int x, int lx, int rx){
if(rx-lx==1){
arr[x] = v;
return;
}
int m = (lx+rx)/2;
if(i<m){
set(i,v,2*x+1,lx,m);
}
else{
set(i,v,2*x+2,m,rx);
}
arr[x] = max(arr[2*x+1],arr[2*x+2]);
}
void set(int i,pii v){
set(i,v,0,0,size);
}
pii query(int l,int r, int x, int lx, int rx){
if(lx>=r||l>=rx)return {0LL,0LL};
if(lx>=l&&rx<=r)return arr[x];
int m = (lx+rx)/2;
pii s1 = query(l,r,2*x+1,lx,m);
pii s2 = query(l,r,2*x+2,m,rx);
return max(s1,s2);
}
pii query(int l, int r){
return query(l,r,0,0,size);
}
};
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
vector<int>l(n+1);
vector<int>r(n+1);
vector<int>sorted;
for(int i = 1; i<=n; i++){
cin >> l[i] >> r[i];
sorted.push_back(l[i]);
sorted.push_back(r[i]);
}
sorted.push_back(-69);
sort(sorted.begin(),sorted.end());
for(int i = 1; i<=n; i++){
l[i] = lower_bound(sorted.begin(),sorted.end(),l[i])-sorted.begin();
r[i] = lower_bound(sorted.begin(),sorted.end(),r[i])-sorted.begin();
}
SegTree left;
SegTree2 right;
left.init(2*n+5);
right.init(2*n+5);
vector<pii>lt(2*n+1,{(int)1e9,(int)1e9});
vector<pii>rt(2*n+1);
vector<vector<int>>lts(2*n+1);
vector<vector<int>>rts(2*n+1);
for(int i = 1; i<=n; i++){
lt[r[i]] = min(lt[r[i]],{l[i],i});
rt[l[i]] = max(rt[l[i]],{r[i],i});
lts[r[i]].push_back(l[i]);
rts[l[i]].push_back(r[i]);
}
for(int i = 1; i<=2*n; i++){
right.set(i,rt[i]);
left.set(i,lt[i]);
}
vector<int>dpl(2*n+5);
vector<int>dpr(2*n+5);
{
int far = 0;
for(int i = 1; i<=2*n; i++){
if(lt[i] == make_pair((int)1e9,(int)1e9)){
dpl[i] = dpl[i-1];
continue;
}
else{
for(int nxt: lts[i]){
far = max(far,nxt);
}
}
auto p = left.query(far,i+1);
dpl[i] = dpl[p.first-1]+1;
}
}
{
int far = 2*n+1;
for(int i = 2*n; i>=1; i--){
if(rt[i] == make_pair(0,0)){
dpr[i] = dpr[i+1];
continue;
}
else{
for(int nxt: rts[i]){
far = min(far,nxt);
}
}
auto p = right.query(i,far+1);
dpr[i] = dpr[p.first+1]+1;
}
}
int best = dpl[2*n];
const int ln = 24;
vector<vector<int>>dp(n+1,vector<int>(ln));
for(int i = 1; i<=n; i++){
auto p = right.query(l[i],r[i]+1);
dp[i][0] = p.second;
}
for(int j = 1; j<ln; j++){
for(int i = 1; i<=n; i++){
dp[i][j] = dp[dp[i][j-1]][j-1];
}
}
// cout << '\n';
// for(int i = 1; i<=n; i++){
// cout << l[i] << ' ' << r[i] << '\n';
// }
// for(int i = 1; i<=2*n; i++){
// cout << dpl[i] << ' ' ;
// }
// cout << '\n';
// for(int i = 1; i<=2*n; i++){
// cout << dpr[i] << ' ' ;
// }
// cout << '\n';
int ans = (int)1e9;
for(int i = 1; i<=n; i++){
int ret = 0;
int u = i;
for(int j = ln-1; j>=0; j--){
int nu = dp[u][j];
if(1 + dpl[l[i]-1] + dpr[r[nu]+1] < best){
continue;
}
u = nu;
ret+=1<<j;
}
if(ret < (1<<22)){
ans = min(ans,ret+1);
}
}
if(ans==(int)1e9){
cout << "impossible\n";
return 0;
}
cout << ans << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
input:
4 1 3 2 5 4 7 6 9
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3484kb
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: 1ms
memory: 3540kb
input:
3 1 2 2 3 3 4
output:
impossible
result:
ok single line: 'impossible'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3496kb
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: 0ms
memory: 3736kb
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: 3488kb
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: 0ms
memory: 3540kb
input:
2 1 2 5 6
output:
impossible
result:
ok single line: 'impossible'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 1 3 2 4
output:
impossible
result:
ok single line: 'impossible'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3572kb
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: 1ms
memory: 3744kb
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: 1ms
memory: 3584kb
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: 0ms
memory: 3796kb
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: 0ms
memory: 3508kb
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: 1ms
memory: 3516kb
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: 0ms
memory: 3684kb
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: 13ms
memory: 7216kb
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: 113ms
memory: 41260kb
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: 119ms
memory: 41272kb
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: 1ms
memory: 3728kb
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: 0ms
memory: 3728kb
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: 0ms
memory: 3564kb
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: 0ms
memory: 3504kb
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: 0ms
memory: 3588kb
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: 0ms
memory: 3760kb
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: 7160kb
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: 118ms
memory: 41404kb
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: 114ms
memory: 41352kb
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: 125ms
memory: 41552kb
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: 119ms
memory: 41640kb
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: 139ms
memory: 42856kb
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: 138ms
memory: 42804kb
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: 145ms
memory: 42780kb
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: 182ms
memory: 46388kb
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: 191ms
memory: 46348kb
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: 195ms
memory: 46380kb
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: 182ms
memory: 46512kb
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: 197ms
memory: 46348kb
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: 164ms
memory: 46412kb
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: -100
Wrong Answer
time: 175ms
memory: 46316kb
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:
3
result:
wrong answer 1st lines differ - expected: '2', found: '3'