QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#117223#4193. Joined SessionswsyearWA 55ms26556kbC++173.4kb2023-06-30 18:20:292023-06-30 18:20:31

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 18:20:31]
  • 评测
  • 测评结果:WA
  • 用时:55ms
  • 内存:26556kb
  • [2023-06-30 18:20:29]
  • 提交

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][2], g[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, a[i].r, 1);
    upd(1, 1, tot, a[i].r, i, 1);
  }
  rep (i, 0, n + 1) rep (j, 0, 3) f[i][j][0] = f[i][j][1] = 1E9;
  f[0][0][0] = 0;
  rep (i, 1, n) rep (j, 0, 3) {
    f[i][j][1] = min(f[lst[i]][j][1], f[lst[i]][j][0]) + 1;
    f[i][j][0] = f[con[i]][j][1];
    int pos = i;
    rep (k, 1, j) {
      pos = con[pos] != n + 1 ? con[pos] : pos;
      f[i][j][0] = min(f[i][j][0], f[pos][j - k][0]);
      f[i][j][1] = min(f[i][j][1], f[pos][j - k][1]);
    }
  }
  int res = min(f[n][0][0], f[n][0][1]);
  rep (i, 1, 3) if (min(f[n][i][0], f[n][i][1]) < res) return write(i), 0;
  puts("impossible");
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 13736kb

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

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

input:

3
1 2
2 3
3 4

output:

impossible

result:

ok single line: 'impossible'

Test #4:

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

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

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

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

input:

2
1 2
5 6

output:

impossible

result:

ok single line: 'impossible'

Test #8:

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

input:

2
1 3
2 4

output:

impossible

result:

ok single line: 'impossible'

Test #9:

score: 0
Accepted
time: 1ms
memory: 13636kb

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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: -100
Wrong Answer
time: 55ms
memory: 26496kb

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:

1

result:

wrong answer 1st lines differ - expected: '3', found: '1'