QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#333822#4270. Double AttendanceMax_s_xaM0 132ms18520kbC++145.0kb2024-02-20 17:00:062024-02-20 17:00:06

Judging History

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

  • [2024-02-20 17:00:06]
  • 评测
  • 测评结果:0
  • 用时:132ms
  • 内存:18520kb
  • [2024-02-20 17:00:06]
  • 提交

answer

#include <iostream>
#include <algorithm>

typedef long long ll;
typedef double lf;

// #define DEBUG 1
struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    #if DEBUG
    #else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
    #endif
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
    #define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')

    template <typename T>
    void Read(T &x)
    {
        #if DEBUG
        std::cin >> x;
        #else
        bool sign = 0; char ch = gc(); x = 0;
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
        if (sign) x = -x;
        #endif
    }
    void Read(char *s)
    {
        #if DEBUG
        std::cin >> s;
        #else
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
        #endif
    }
    void Read(char &c) {for (c = gc(); blank(c); c = gc());}

    void Push(const char &c)
    {
        #if DEBUG
        putchar(c);
        #else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
        #endif
    }
    template <typename T>
    void Write(T x)
    {
        if (x < 0) x = -x, Push('-');
        static T sta[35];
        int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) Push(sta[--top] ^ 48);
    }
    template <typename T>
    void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)

using namespace std;

const int MAXN = 3e5 + 10;

int n1, n2, d;
struct Seg
{
    int l, r;
    bool operator < (const Seg u) const {return l < u.l;}
}a[MAXN], b[MAXN];

#define nxta(x) upper_bound(a + 1, a + n1 + 1, Seg{x, 0}) - a
#define nxtb(x) upper_bound(b + 1, b + n2 + 1, Seg{x, 0}) - b
#define posa(p, x) (p > n1 ? 2e9 : max(a[p].l, x))
#define posb(p, x) (p > n2 ? 2e9 : max(b[p].l, x))
inline int sufa(int x, int pre)
{
    x += d, pre -= d;
    int cur = upper_bound(a + 1, a + n1 + 1, Seg{x, 0}) - a - 1;
    if (cur == 0 || a[cur].r < x || pre >= a[cur].l) cur++;
    return cur;
}
inline int sufb(int x, int pre)
{
    x += d, pre -= d;
    int cur = upper_bound(b + 1, b + n2 + 1, Seg{x, 0}) - b - 1;
    if (cur == 0 || b[cur].r < x || pre >= b[cur].l) cur++;
    return cur;
}

int g[2][MAXN << 1], h[2][MAXN << 1], tp[2];

int main()
{
    // freopen("C.in", "r", stdin);
    // freopen("C.out", "w", stdout);
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    Read(n1), Read(n2), Read(d);
    for (int i = 1; i <= n1; i++) Read(a[i].l), Read(a[i].r), a[i].r--;
    for (int i = 1; i <= n2; i++) Read(b[i].l), Read(b[i].r), b[i].r--;
    a[n1 + 1].l = b[n2 + 1].l = 2e9;
    sort(a + 1, a + n1 + 1), sort(b + 1, b + n2 + 1);
    int p1 = nxta(-1), p2 = nxtb(d - 1);
    if (b[p2].l == d - 1) p2++;
    int x1 = posa(p1, 0), x2 = posb(p2, d);
    g[0][0] = 0, g[1][0] = d;
    if (x1 <= x2) tp[0]++, g[0][tp[0]] = x1, h[0][tp[0]] = 0;
    if (x2 <= x1 || x2 == d) tp[1] += 1 + (x1 == 0), g[1][tp[1]] = x2, h[1][tp[1]] = d;
    if (tp[1] == 2) g[1][1] = d;
    while (1)
    {
        int p1 = nxta(g[0][tp[0]]), x1 = posa(p1, g[0][tp[0]]), l1 = h[0][tp[0]];
        if (tp[1] > tp[0] && x1 > g[1][tp[0] + 1] + d) x1 = l1 = g[1][tp[0] + 1] + d;
        if (tp[1] >= tp[0])
        {
            int p = sufa(g[1][tp[0]], h[1][tp[0]]), x = posa(p, g[1][tp[0]] + d), l = g[1][tp[0]] + d;
            if (x1 > x || (x == x1 && l1 > l)) x1 = x, l1 = l;
        }
        int p2 = nxtb(g[1][tp[1]]), x2 = posb(p2, g[1][tp[1]]), l2 = h[1][tp[1]];
        if (tp[0] > tp[1] && x2 > g[0][tp[1] + 1] + d) x2 = l2 = g[0][tp[1] + 1] + d;
        if (tp[0] >= tp[1])
        {
            int p = sufb(g[0][tp[1]], h[0][tp[1]]), x = posb(p, g[0][tp[1]] + d), l = g[0][tp[1]] + d;
            if (x2 > x || (x == x2 && l2 > l)) x2 = x, l2 = l;
        }
        if (x1 == 2e9 && x2 == 2e9) break;
        // cout << x1 << ' ' << tp[0] + 1 << ' ' << l1 << '\n';
        // cout << x2 << ' ' << tp[1] + 1 << ' ' << l2 << '\n';
        // cout << '\n';
        if (x1 <= x2) tp[0]++, g[0][tp[0]] = x1, h[0][tp[0]] = l1;
        if (x2 <= x1) tp[1]++, g[1][tp[1]] = x2, h[1][tp[1]] = l2;
    }
    cout << max(tp[0], tp[1]) << '\n';
    // for (int i = 1; i <= n1; i++) cout << a[i].l << ' ' << a[i].r << '\n'; cout << '\n';
    // for (int i = 1; i <= n2; i++) cout << b[i].l << ' ' << b[i].r << '\n'; cout << '\n';
    // for (int i = 1; i <= tp[0]; i++) cout << g[0][i] << ' ' << h[0][i] << '\n';
    // cout << '\n';
    // for (int i = 1; i <= tp[1]; i++) cout << g[1][i] << ' ' << h[1][i] << '\n';
    // cout << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 2ms
memory: 13948kb

input:

3 1 8
10 20
100 101
20 21
15 25

output:

3

result:

ok single line: '3'

Test #2:

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

input:

1 5 3
1 100
1 2
2 3
3 4
4 5
5 6

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 2ms
memory: 15860kb

input:

10 10 5
4 9
43 48
69 70
70 72
52 67
75 83
100 103
103 1501
10 27
28 40
5 7
27 29
30 39
40 42
42 45
67 80
0 5
45 59
10 20
22 23

output:

18

result:

ok single line: '18'

Test #4:

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

input:

1 1 1
0 1
0 1

output:

1

result:

ok single line: '1'

Test #5:

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

input:

1 10 2
1 2000
4 5
10 11
7 8
3 4
9 10
1 2
2 3
8 9
6 7
5 6

output:

10

result:

ok single line: '10'

Test #6:

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

input:

10 10 90
1440 1620
0 180
1080 1260
900 1080
180 360
720 900
540 720
360 540
1620 1800
1260 1440
1170 1350
990 1170
1530 1710
1350 1530
90 270
450 630
270 450
630 810
810 990
1710 1890

output:

20

result:

ok single line: '20'

Test #7:

score: 0
Accepted
time: 2ms
memory: 15920kb

input:

10 10 90
1080 1260
1440 1620
900 1080
1620 1800
180 360
360 540
540 720
1800 1980
1260 1440
720 900
90 270
1710 1890
810 990
1170 1350
1530 1710
630 810
1350 1530
990 1170
450 630
270 450

output:

20

result:

ok single line: '20'

Test #8:

score: 0
Accepted
time: 2ms
memory: 13812kb

input:

10 10 166
1 2
664 996
332 664
1660 1992
0 1
1328 1660
996 1328
3 4
2 3
4 5
333 334
1494 1826
498 830
1162 1494
334 335
336 337
0 332
830 1162
335 336
332 333

output:

20

result:

ok single line: '20'

Test #9:

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

input:

10 10 166
2 3
0 1
3 4
1328 1660
1999 2000
996 1328
1 2
332 664
4 5
664 996
334 335
335 336
333 334
1162 1494
0 332
498 830
336 337
830 1162
332 333
1999 2000

output:

19

result:

ok single line: '19'

Test #10:

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

input:

10 10 1
1607 1721
327 413
222 264
1744 1746
35 50
619 766
995 1127
1421 1541
1236 1294
984 995
626 1122
1313 1386
65 141
1394 1428
1553 1764
1766 1990
1551 1552
465 531
1500 1531
623 625

output:

20

result:

ok single line: '20'

Test #11:

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

input:

10 10 1000000000
664 1247
157 183
1975 1986
1289 1374
1448 1461
233 326
1888 1913
183 194
1927 1933
1499 1672
1138 1387
402 652
266 396
1439 1452
1954 1956
684 737
1700 1887
1576 1678
1473 1485
886 1004

output:

10

result:

ok single line: '10'

Test #12:

score: 0
Accepted
time: 2ms
memory: 15840kb

input:

10 10 3
786 792
1395 1579
1348 1371
303 371
430 431
1331 1343
813 1050
1833 1853
654 706
622 634
237 302
1261 1266
49 216
1514 1524
1524 1607
1004 1018
748 918
1020 1141
1967 1994
1710 1735

output:

20

result:

ok single line: '20'

Test #13:

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

input:

10 10 4
82 206
370 769
1086 1131
267 330
836 984
995 1052
778 805
1880 1956
1956 1999
1531 1761
1687 1730
1879 1968
694 710
441 674
738 1302
1734 1737
1357 1365
1372 1604
1606 1672
722 726

output:

20

result:

ok single line: '20'

Test #14:

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

input:

10 10 9
1667 1724
266 375
1736 1936
1312 1659
858 886
442 708
193 198
1127 1244
383 428
935 1021
614 628
1797 1832
199 218
229 268
386 404
413 587
962 1248
814 878
1462 1732
1420 1424

output:

20

result:

ok single line: '20'

Test #15:

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

input:

10 10 16
14 88
1638 1644
645 970
1218 1232
1401 1589
1972 1994
1657 1721
1145 1188
1243 1246
179 244
1925 1958
355 433
706 832
564 587
12 270
1541 1728
1499 1529
294 348
1160 1205
1004 1032

output:

20

result:

ok single line: '20'

Test #16:

score: -5
Wrong Answer
time: 0ms
memory: 15908kb

input:

10 10 64
998 1233
1868 1888
1898 1943
1811 1818
243 292
185 202
205 211
342 454
1269 1313
970 973
770 1192
1424 1435
710 715
60 74
77 250
1992 1998
715 758
1393 1397
1523 1695
359 439

output:

19

result:

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

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #104:

score: 6
Accepted
time: 0ms
memory: 13888kb

input:

1 1 1
0 1
0 1

output:

1

result:

ok single line: '1'

Test #105:

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

input:

1 2000 2
999999996 1000000000
336 337
502 503
1906 1907
963 964
1351 1352
1795 1796
1510 1511
304 305
1930 1931
1735 1736
1469 1470
338 339
813 814
182 183
209 210
321 322
849 850
721 722
394 395
889 890
1758 1759
1440 1441
560 561
1470 1471
1916 1917
793 794
1366 1367
158 159
1602 1603
214 215
1119...

output:

2000

result:

ok single line: '2000'

Test #106:

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

input:

2000 2000 249875
608195750 608695500
88455750 88955500
579210250 579710000
817091250 817591000
527736000 528235750
52473750 52973500
89955000 90454750
184407750 184907500
668165750 668665500
24487750 24987500
466266750 466766500
471764000 472263750
212393750 212893500
250874500 251374250
939530000 9...

output:

4000

result:

ok single line: '4000'

Test #107:

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

input:

2000 2000 249875
965017250 965517000
73963000 74462750
242878500 243378250
148925500 149425250
747126250 747626000
384307750 384807500
655172250 655672000
278360750 278860500
899050250 899550000
496251750 496751500
92953500 93453250
677661000 678160750
828085750 828585500
297351250 297851000
5887055...

output:

4000

result:

ok single line: '4000'

Test #108:

score: 0
Accepted
time: 2ms
memory: 13836kb

input:

2000 2000 499500
428 429
764235000 765234000
511488000 512487000
291 292
585414000 586413000
127 128
819 820
727 728
233766000 234765000
643 644
234 235
326 327
432 433
218781000 219780000
10989000 11988000
805194000 806193000
283716000 284715000
965034000 966033000
632367000 633366000
824 825
454 4...

output:

4000

result:

ok single line: '4000'

Test #109:

score: 0
Accepted
time: 2ms
memory: 13836kb

input:

2000 2000 499500
175 176
766233000 767232000
230 231
925 926
844 845
681318000 682317000
48951000 49950000
757 758
266 267
438561000 439560000
262737000 263736000
813 814
915084000 916083000
485514000 486513000
214785000 215784000
532467000 533466000
25 26
41958000 42957000
534 535
331 332
53 54
732...

output:

3999

result:

ok single line: '3999'

Test #110:

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

input:

2000 2000 1
97918740 97918742
612788646 612788648
709014683 709014684
550596486 550596488
611820813 611820815
742133170 742133172
999593290 999593292
65695562 65695563
984598976 984598977
285428771 285428773
334881813 334881814
751309389 751309390
635034524 635034526
202056719 202056720
472216430 47...

output:

4000

result:

ok single line: '4000'

Test #111:

score: -6
Wrong Answer
time: 132ms
memory: 18520kb

input:

2000 2000 1000000000
762582513 763402869
685982674 685994777
607586653 607621748
725505868 725606928
287661547 287711487
961278566 961422544
282891861 282922769
388240582 388471546
305173664 305545845
17696180 17939334
267223086 267237726
251362344 251735629
957622587 957813570
321979347 321992100
7...

output:

1202001

result:

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

Subtask #4:

score: 0
Skipped

Dependency #1:

0%