Submission #3443314


Source Code Expand

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable int MAX = 10^^5+10;

void main() {
    auto N = readln.chomp.to!int;
    auto A = N.iota.map!(_ => readln.split.map!(to!int).array).array;

    auto B = new int[](MAX);
    foreach (a; A) B[a[0]] += 1, B[a[1]] -= 1;
    foreach (i; 0..MAX-1) B[i+1] += B[i];

    auto st = new SegmentTree!(int, (a, b) => max(a, b), 0)(MAX);
    foreach (i; 0..MAX) st.update(i, B[i]);

    long ans = 1L << 59;

    foreach (a; A) {
        long tmp1 = st.query(0, a[0]-1);
        long tmp2 = st.query(a[0], a[1]-1) - 1;
        long tmp3 = st.query(a[1], MAX-1);
        ans = min(ans, max(tmp1, tmp2, tmp3));
    }

    ans.writeln;
}



class SegmentTree(T, alias op, T e) {
    T[] table;
    int size;
    int offset;

    this(int n) {
        size = 1;
        while (size <= n) size <<= 1;
        size <<= 1;
        table = new T[](size);
        fill(table, e);
        offset = size / 2;
    }

    void update(int pos, T val) {
        pos += offset;
        table[pos] = val;
        while (pos > 1) {
            pos /= 2;
            table[pos] = op(table[pos*2], table[pos*2+1]);
        }
    }

    T query(int l, int r) {
        return query(l, r, 1, 0, offset-1);
    }

    T query(int l, int r, int i, int a, int b) {
        if (b < l || r < a) {
            return e;
        } else if (l <= a && b <= r) {
            return table[i];
        } else {
            return op(query(l, r, i*2, a, (a+b)/2), query(l, r, i*2+1, (a+b)/2+1, b));
        }
    }
}

Submission Info

Submission Time
Task D - 足ゲームII
User nebukuro09
Language D (LDC 0.17.0)
Score 100
Code Size 1741 Byte
Status AC
Exec Time 224 ms
Memory 12668 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 34
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 7 ms 3196 KB
01-02.txt AC 7 ms 3708 KB
01-03.txt AC 7 ms 2556 KB
01-04.txt AC 9 ms 2940 KB
01-05.txt AC 222 ms 11644 KB
01-06.txt AC 222 ms 11644 KB
01-07.txt AC 222 ms 11644 KB
01-08.txt AC 222 ms 11772 KB
01-09.txt AC 222 ms 12668 KB
01-10.txt AC 8 ms 3324 KB
01-11.txt AC 222 ms 11644 KB
01-12.txt AC 222 ms 11644 KB
01-13.txt AC 222 ms 11644 KB
01-14.txt AC 224 ms 12284 KB
01-15.txt AC 12 ms 2940 KB
01-16.txt AC 222 ms 11900 KB
01-17.txt AC 222 ms 11644 KB
01-18.txt AC 222 ms 11644 KB
01-19.txt AC 222 ms 12412 KB
01-20.txt AC 11 ms 2812 KB
01-21.txt AC 222 ms 11644 KB
01-22.txt AC 222 ms 12284 KB
01-23.txt AC 220 ms 11644 KB
01-24.txt AC 172 ms 12412 KB
01-25.txt AC 7 ms 2428 KB
01-26.txt AC 7 ms 1660 KB
01-27.txt AC 200 ms 11644 KB
01-28.txt AC 199 ms 11644 KB
sample-01.txt AC 7 ms 2940 KB
sample-02.txt AC 7 ms 3068 KB
sample-03.txt AC 7 ms 1660 KB