QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#116929#4193. Joined SessionswsyearAC ✓66ms23392kbC++143.3kb2023-06-30 10:54:032023-06-30 10:54:04

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-30 10:54:04]
  • 评测
  • 测评结果:AC
  • 用时:66ms
  • 内存:23392kb
  • [2023-06-30 10:54:03]
  • 提交

answer

/*
* Author: Enucai
* Date: 2022-12-13 09:51:34
* LastEditTime: 2023-06-29 20:21:13
*/

#include <bits/stdc++.h>
#ifdef dbg
#define D(...) fprintf(stderr, __VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ " = "), debug_helper::debug(__VA_ARGS__), D("\n")
#include "C:\Users\wsyear\Desktop\OI\templates\debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define gc getchar
#define pc putchar
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

using namespace std;

template <class T = int> T read() {
  T x = 0; bool f = 0; char ch = gc();
  while (!isdigit(ch)) f = ch == '-', ch = gc();
  while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc();
  return f ? -x: x;
}
template <class T> void write(T x) {
  if (x >= 0) { if (x > 9) write(x / 10); pc(x % 10 + 48); }
  else { pc('-'); if (x < -9) write(-x / 10); pc(48 - x % 10); }
}

const int N = 1000010;
const int M = 2000010;

struct SegMent {
  int l, r;
} a[N];

int n, tot, c[M], f[N][4], lst[N], con[N], t[M << 2];

int mo(int op, int x, int y) {
  if (op) return min(x, y);
  else return max(x, y);
}

#define mid ((l + r) >> 1)

void upd(int c, int l, int r, int x, int v, int o) {
  if (l == r) return t[c] = mo(o, t[c], v), void();
  if (x <= mid) upd(c << 1, l, mid, x, v, o);
  else upd(c << 1 | 1, mid + 1, r, x, v, o);
  t[c] = mo(o, t[c << 1], t[c << 1 | 1]);
}

int qry(int c, int l, int r, int x, int y, int o) {
  if (l == x && r == y) return t[c];
  if (y <= mid) return qry(c << 1, l, mid, x, y, o);
  else if (x > mid) return qry(c << 1 | 1, mid + 1, r, x, y, o);
  else return mo(o, qry(c << 1, l, mid, x, mid, o), qry(c << 1 | 1, mid + 1, r, mid + 1, y, o));
}

#undef mid

int main() {
  n = read();
  rep (i, 1, n) a[i].l = read(), a[i].r = read();
  sort(a + 1, a + n + 1, [&](SegMent x, SegMent y) {
    return x.l == y.l ? x.r < y.r : x.l < y.l;
  });
  bool flag = 0;
  rep (i, 1, n - 1) if (a[i].r >= a[i + 1].l) flag = 1;
  if (!flag) return puts("impossible"), 0;
  rep (i, 1, n) c[2 * i - 1] = a[i].l, c[2 * i] = a[i].r;
  sort(c + 1, c + 2 * n + 1);
  tot = unique(c + 1, c + 2 * n + 1) - c - 1;
  rep (i, 1, n) {
    a[i].l = lower_bound(c + 1, c + tot + 1, a[i].l) - c;
    a[i].r = lower_bound(c + 1, c + tot + 1, a[i].r) - c;
  }
  rep (i, 1, tot << 2) t[i] = 0;
  rep (i, 1, n) {
    if (a[i].l != 1) lst[i] = qry(1, 1, tot, 1, a[i].l - 1, 0);
    upd(1, 1, tot, a[i].r, i, 0);
  }
  rep (i, 1, tot << 2) t[i] = n + 1;
  rep (i, 1, n) {
    con[i] = qry(1, 1, tot, a[i].l, tot, 1);
    upd(1, 1, tot, a[i].r, i, 1);
  }
  rep (i, 1, n) if (con[i] == n + 1) con[i] = i;
  rep (i, 0, n + 1) rep (j, 0, 3) f[i][j] = 1E9;
  rep (j, 0, 3) rep (i, 1, n) {
    if (!lst[i]) f[i][j] = 1;
    else {
      int pos = i;
      rep (k, 0, j) {
        pos = con[pos];
        if (!lst[pos]) {
          f[i][j] = 1;
          break;
        }
        f[i][j] = min(f[i][j], f[lst[pos]][j - k] + 1);
      }
    }
  }
  rep (i, 1, 3) if (f[n][i] < f[n][0]) return write(i), 0;
  puts("impossible");
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 13624kb

input:

4
1 3
2 5
4 7
6 9

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 3ms
memory: 13508kb

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: 13716kb

input:

3
1 2
2 3
3 4

output:

impossible

result:

ok single line: 'impossible'

Test #4:

score: 0
Accepted
time: 3ms
memory: 13628kb

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: 13628kb

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: 13740kb

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: 5432kb

input:

2
1 2
5 6

output:

impossible

result:

ok single line: 'impossible'

Test #8:

score: 0
Accepted
time: 0ms
memory: 13800kb

input:

2
1 3
2 4

output:

impossible

result:

ok single line: 'impossible'

Test #9:

score: 0
Accepted
time: 0ms
memory: 13628kb

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: 2ms
memory: 13632kb

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: 13632kb

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: 13620kb

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: 1ms
memory: 13632kb

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: 13740kb

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: 3ms
memory: 13584kb

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: 7ms
memory: 13648kb

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: 28ms
memory: 15772kb

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: 38ms
memory: 17744kb

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: 3ms
memory: 13632kb

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: 3ms
memory: 13576kb

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: 13628kb

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: 13628kb

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: 3ms
memory: 13640kb

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: 3ms
memory: 13632kb

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: 8ms
memory: 15724kb

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: 34ms
memory: 15656kb

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: 35ms
memory: 19804kb

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: 37ms
memory: 15844kb

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: 37ms
memory: 19812kb

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: 46ms
memory: 18704kb

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: 46ms
memory: 16836kb

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: 39ms
memory: 20736kb

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: 56ms
memory: 23188kb

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: 61ms
memory: 23392kb

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: 66ms
memory: 21584kb

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: 19768kb

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: 63ms
memory: 22260kb

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: 56ms
memory: 23284kb

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: 61ms
memory: 19572kb

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: 58ms
memory: 19672kb

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: 64ms
memory: 21152kb

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: 59ms
memory: 22284kb

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'