結果

問題 No.3446 Range Adjacent Differences
ユーザー 👑 ArcAki
提出日時 2026-02-12 13:46:17
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 7,709 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,753 ms
コンパイル使用メモリ 359,672 KB
実行使用メモリ 187,288 KB
最終ジャッジ日時 2026-02-18 20:51:05
合計ジャッジ時間 9,102 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:148:9: warning: 'L' may be used uninitialized [-Wmaybe-uninitialized]
  148 |         --L; --R;
      |         ^~~
main.cpp:145:13: note: 'L' was declared here
  145 |         int L, R, X;
      |             ^
main.cpp:148:14: warning: 'R' may be used uninitialized [-Wmaybe-uninitialized]
  148 |         --L; --R;
      |              ^~~
main.cpp:145:16: note: 'R' was declared here
  145 |         int L, R, X;
      |                ^
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/algorithm:62,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/x86_64-pc-linux-gnu/bits/stdc++.h:53,
                 from main.cpp:1:
In function 'constexpr const _Tp& std::max(const _Tp&, const _Tp&) [with _Tp = int]',
    inlined from 'int main()' at main.cpp:150:19:
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_algobase.h:263:7: warning: 'X' may be used uninitialized [-Wmaybe-uninitialized]
  263 |       if (__a < __b)
      |       ^~
main.cpp: In function 'int main()':
main.cpp:145:19: note: 'X' was declared here
  145 |         int L, R, X;
      |                   ^
main.cpp:149:15: warning: 'c' may be used uninitialized [-Wmaybe-uninitialized]
  149 |         qs[i] = {L, R, X, c, i};
main.cpp:146:14: note: 'c' was declared here
  146 |         char c;
      |              ^

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

// ---------------- Fast Input ----------------
struct FastScanner {
    static constexpr size_t BUFSIZE = 1 << 20;
    int idx = 0, size = 0;
    char buf[BUFSIZE];

    inline char read() {
        if (idx >= size) {
            size = (int)fread(buf, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) return 0;
        }
        return buf[idx++];
    }

    template <class T>
    inline bool readInt(T &out) {
        char c;
        do { c = read(); if (!c) return false; } while (c <= ' ');
        T sign = 1;
        if (c == '-') { sign = -1; c = read(); }
        T val = 0;
        while (c > ' ') {
            val = val * 10 + (c - '0');
            c = read();
        }
        out = val * sign;
        return true;
    }

    inline bool readChar(char &out) {
        char c;
        do { c = read(); if (!c) return false; } while (c <= ' ');
        out = c;
        return true;
    }
};

// ---------------- Presence SegTree (0/1) with prev/next ----------------
struct SegTreePresence {
    int size0 = 0;
    int n = 1;
    vector<int> seg; // sums (>=0)

    SegTreePresence() {}
    SegTreePresence(int sz) { init(sz); }

    void init(int sz) {
        size0 = sz;
        n = 1;
        while (n < sz) n <<= 1;
        seg.assign(2 * n, 0);
    }

    inline int total() const { return seg[1]; }

    inline void set01(int pos, int val) { // val is 0/1
        int i = pos + n;
        if (seg[i] == val) return;
        seg[i] = val;
        for (i >>= 1; i; i >>= 1) seg[i] = seg[i<<1] + seg[i<<1|1];
    }

    // largest index <= x with leaf==1, else -1
    inline int prev_leq(int x) const {
        if (size0 <= 0) return -1;
        if (x < 0) return -1;
        if (x >= size0) x = size0 - 1;

        int i = x + n;
        if (seg[i]) return x;

        while (i > 1) {
            if (i & 1) { // right child
                if (seg[i - 1]) {
                    i = i - 1;
                    while (i < n) {
                        int rc = (i<<1)|1;
                        if (seg[rc]) i = rc;
                        else i = (i<<1);
                    }
                    return i - n;
                }
            }
            i >>= 1;
        }
        return -1;
    }

    // smallest index >= x with leaf==1, else size0
    inline int next_geq(int x) const {
        if (size0 <= 0) return 0;
        if (x < 0) x = 0;
        if (x >= size0) return size0;

        int i = x + n;
        if (seg[i]) return x;

        while (i > 1) {
            if ((i & 1) == 0) { // left child
                if (seg[i + 1]) {
                    i = i + 1;
                    while (i < n) {
                        int lc = (i<<1);
                        if (seg[lc]) i = lc;
                        else i = lc | 1;
                    }
                    return i - n;
                }
            }
            i >>= 1;
        }
        return size0;
    }
};

// ---------------- Mo Query ----------------
struct Query {
    int l, r;   // inclusive 0-indexed
    int x;
    char c;     // 'L' or 'R'
    int idx;
};

int main() {
    FastScanner fs;

    int N, Q;
    if (!fs.readInt(N)) return 0;
    fs.readInt(Q);

    vector<int> A(N);
    int maxA = 0;
    for (int i = 0; i < N; i++) {
        fs.readInt(A[i]);
        maxA = max(maxA, A[i]);
    }

    vector<Query> qs(Q);
    int maxX = 0;
    for (int i = 0; i < Q; i++) {
        int L, R, X;
        char c;
        fs.readInt(L); fs.readInt(R); fs.readInt(X); fs.readChar(c);
        --L; --R;
        qs[i] = {L, R, X, c, i};
        maxX = max(maxX, X);
    }

    // ---- Coordinate compression ONLY for A-values ----
    vector<int> comp = A;
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    int M = (int)comp.size(); // <= N

    vector<int> Aid(N);
    for (int i = 0; i < N; i++) {
        Aid[i] = (int)(lower_bound(comp.begin(), comp.end(), A[i]) - comp.begin());
    }

    // ---- Gap domain remains 0..maxV ----
    int maxV = max(maxA, maxX);
    int SZG = maxV + 1; // gaps are in [0..maxV]

    // ---- Mo ordering ----
    int B = max(1, (int)(N / max(1.0, sqrt((double)Q))));
    sort(qs.begin(), qs.end(), [&](const Query& a, const Query& b) {
        int ab = a.l / B, bb = b.l / B;
        if (ab != bb) return ab < bb;
        if (ab & 1) return a.r > b.r;
        else        return a.r < b.r;
    });

    // ---- Structures ----
    vector<uint32_t> cntVal(M, 0);       // counts per compressed id
    SegTreePresence segVal(M);           // presence of distinct values (id)

    vector<uint32_t> cntGap(SZG, 0);     // counts per gap value
    SegTreePresence segGap(SZG);         // presence of distinct gaps (d)

    auto add_gap = [&](int d) {
        auto &c = cntGap[d];
        if (c++ == 0) segGap.set01(d, 1);
    };
    auto remove_gap = [&](int d) {
        auto &c = cntGap[d];
        if (--c == 0) segGap.set01(d, 0);
    };

    auto add_value = [&](int id) {
        int v = comp[id];

        int predId = segVal.prev_leq(id - 1); // distinct < v
        bool hasV = (cntVal[id] > 0);
        int succId = hasV ? id : segVal.next_geq(id); // distinct >= v (or itself)

        const int INFID = M;

        if (predId != -1 && succId != INFID) {
            int L = comp[predId];
            int R = comp[succId];
            remove_gap(R - L);
            add_gap(v - L);
            add_gap(R - v);
        } else if (predId != -1) {
            int L = comp[predId];
            add_gap(v - L);
        } else if (succId != INFID) {
            int R = comp[succId];
            add_gap(R - v);
        }

        if (cntVal[id]++ == 0) segVal.set01(id, 1);
    };

    auto remove_value = [&](int id) {
        int v = comp[id];

        int predId = segVal.prev_leq(id - 1);
        bool remains = (cntVal[id] >= 2); // after removing one, still exists?
        const int INFID = M;
        int succId = remains ? id : segVal.next_geq(id + 1); // next distinct > v if disappears

        if (predId != -1 && succId != INFID) {
            int L = comp[predId];
            int R = comp[succId];
            remove_gap(v - L);
            remove_gap(R - v);
            add_gap(R - L);
        } else if (predId != -1) {
            int L = comp[predId];
            remove_gap(v - L);
        } else if (succId != INFID) {
            int R = comp[succId];
            remove_gap(R - v);
        }

        if (--cntVal[id] == 0) segVal.set01(id, 0);
    };

    vector<int> ans(Q, -1);

    int curL = 0, curR = -1;
    for (const auto& qu : qs) {
        while (curL > qu.l) add_value(Aid[--curL]);
        while (curR < qu.r) add_value(Aid[++curR]);
        while (curL < qu.l) remove_value(Aid[curL++]);
        while (curR > qu.r) remove_value(Aid[curR--]);

        if (segGap.total() == 0) {
            ans[qu.idx] = -1;
            continue;
        }

        int x = qu.x;
        if (qu.c == 'L') {
            int d = segGap.prev_leq(x);
            ans[qu.idx] = (d == -1 ? -1 : d);
        } else { // 'R'
            int d = segGap.next_geq(x);
            ans[qu.idx] = (d == SZG ? -1 : d);
        }
    }

    // ---- Fast output ----
    string out;
    out.reserve((size_t)Q * 12);
    auto push_int = [&](int x) {
        if (x == 0) { out += "0\n"; return; }
        if (x < 0) { out.push_back('-'); x = -x; }
        char s[16];
        int n = 0;
        while (x) { s[n++] = char('0' + (x % 10)); x /= 10; }
        while (n--) out.push_back(s[n]);
        out.push_back('\n');
    };
    for (int i = 0; i < Q; i++) push_int(ans[i]);
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}
0