結果

問題 No.674 n連勤
コンテスト
ユーザー nanae
提出日時 2018-04-30 11:40:54
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 130 ms / 2,000 ms
コード長 3,014 bytes
コンパイル時間 1,009 ms
コンパイル使用メモリ 118,116 KB
実行使用メモリ 10,908 KB
最終ジャッジ日時 2024-06-13 00:57:38
合計ジャッジ時間 2,474 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.d(28): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`

ソースコード

diff # 

import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons;
import std.math, std.numeric;

alias Seg = Tuple!(long, "l", long, "r");

void main() {
    long d; int q; scan(d, q);

    long[] a;
    Seg[]  ss = new Seg[](q);

    foreach (i ; 0 .. q) {
        long li, ri;
        scan(li, ri); ri++;
        ss[i] = Seg(li, ri);
        a ~= li; a ~= ri;
    }

    a = a.sort().uniq().array;

    debug {
        writeln("a:", a);
    }

    int[long] map;
    long[] rmap = new long[](2*q);
    foreach (int i, ai; a) {
        map[ai] = i;
        rmap[i] = ai;
    }

    debug {
        writeln("map:", map);
        writeln("rmap:", rmap);
    }

    auto sd = SqrtDecomp(2*q);

    long ans;

    foreach (i ; 0 .. q) {
        int l = min(map[ss[i].l], sd.query(map[ss[i].l]).l.to!int);
        int r = max(map[ss[i].r], sd.query(map[ss[i].r]).r.to!int);
        ans = max(ans, rmap[r] - rmap[l]);
        sd.update(l, r + 1, Seg(l, r));
        writeln(ans);

        debug {
            writefln("(%d, %d)", l, r);
            writeln(sd.bucket);
            writeln(sd.data);
        }
    }
}



struct SqrtDecomp {
    private {
        enum root = 512;
        enum inf  = 10^^9;
        Seg[] data; int N;
        Seg[] bucket; int K;
    }

    this(int n) {
        K = (n + root - 1) / root;
        N = K * root;
        data = new Seg[](N);
        data[] = Seg(inf, -inf);
        bucket = new Seg[](K);
        bucket[] = Seg(inf, -inf);
    }

    Seg query(int x) {
        int k = x / root;
        if (bucket[k].l == inf) {
            return data[x];
        }
        else {
            foreach (i ; k * root .. (k + 1) * root) {
                data[i] = bucket[k];
            }
            bucket[k] = Seg(inf, -inf);
            return data[x];
        }
    }

    void update(int l, int r, Seg s) {
        foreach (k ; 0 .. K) {
            int lb = k * root, rb = (k + 1) * root;
            if (r <= lb || rb <= l) continue;
            if (l <= lb && rb <= r) {
                bucket[k] = s;
            }
            else {
                if (bucket[k].l != inf) {
                    foreach (i ; k*root .. (k+1)*root) {
                        data[i] = bucket[k];
                    }
                    bucket[k] = Seg(inf, -inf);
                }
                foreach (i ; max(l, lb) .. min(r, rb)) {
                    data[i] = s;
                }
            }
        }
    }
}






void scan(T...)(ref T args) {
    import std.stdio : readln;
    import std.algorithm : splitter;
    import std.conv : to;
    import std.range.primitives;

    auto line = readln().splitter();
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}
0