結果

問題 No.2223 Merged Med
ユーザー 👑 NachiaNachia
提出日時 2023-02-17 23:15:51
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,013 bytes
コンパイル時間 1,050 ms
コンパイル使用メモリ 92,292 KB
実行使用メモリ 31,824 KB
最終ジャッジ日時 2024-07-19 14:26:42
合計ジャッジ時間 13,256 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,948 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 145 ms
30,936 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 AC 258 ms
31,076 KB
testcase_31 AC 257 ms
29,820 KB
testcase_32 AC 11 ms
6,944 KB
testcase_33 AC 528 ms
30,972 KB
testcase_34 AC 531 ms
31,604 KB
testcase_35 AC 535 ms
31,240 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <atcoder/modint>
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;

using Modint = atcoder::static_modint<998244353>;


template<
    class S,
    S(*op)(S a, S b),
    S(*e)()
>
struct persistent_segtree {
    struct Node { int l, r; S v; };
    int N, logN;
    vector<Node> V;
    void merge(int p) { V[p].v = op(V[V[p].l].v, V[V[p].r].v); }
    persistent_segtree(int z = 0) {
        N = 1; logN = 0; while (N < z) { N *= 2; logN++; }
        V.assign(N * 2 - 1, { -1,-1,e() });
        for (int i = N - 2; i >= 0; i--) { V[i].l = i * 2 + 1; V[i].r = i * 2 + 2; }
    }
    persistent_segtree(const vector<S>& v)
        : persistent_segtree(v.size()) {
        rep(i, v.size()) V[N - 1 + i].v = v[i];
        for (int i = N - 2; i >= 0; i--) merge(i);
    }
    int copy_node(int p) { V.push_back(V[p]); return V.size() - 1; }
    int set(int t, int p, S v) {
        vector<int> P;
        P.push_back(copy_node((t == -1) ? 0 : t));
        for (int d = logN - 1; d >= 0; d--) {
            int pp = P.back();
            if (p & (1 << d)) { P.push_back(copy_node(V[pp].r)); V[pp].r = P.back(); }
            else { P.push_back(copy_node(V[pp].l)); V[pp].l = P.back(); }
            pp = P.back();
        }
        V[P.back()].v = v;
        for (int i = P.size() - 2; i >= 0; i--) merge(P[i]);
        return P.front();
    }
    int where(int t, int p) {
        int s = (t == -1) ? 0 : t;
        for (int d = logN - 1; d >= 0; d--) s = ((p & (1 << d)) ? V[s].r : V[s].l);
        return s;
    }
    S get(int t, int p) {
        int s = (t == -1) ? 0 : t;
        for (int d = logN - 1; d >= 0; d--) s = ((p & (1 << d)) ? V[s].r : V[s].l);
        return V[s].v;
    }
    S prod(int t, int l, int r) {
        struct DFSV { int l, r, i; };
        vector<DFSV> G; G.reserve(logN * 2 + 2);
        int s = (t == -1) ? 0 : t;
        G.push_back({ 0,N,s });
        S res = e();
        while (G.size()) {
            DFSV g = G.back(); G.pop_back();
            int a = g.l, b = g.r, i = g.i;
            if (r <= a || b <= l) continue;
            if (l <= a && b <= r) { res = op(res, V[i].v); continue; }
            G.push_back({ (a + b) / 2,b,V[i].r });
            G.push_back({ a,(a + b) / 2,V[i].l });
        }
        return res;
    }
};

struct S{
    int lsummin, rsummin, sum;
    bool e;
};
S op(S l, S r){
    if(l.e) return r;
    if(r.e) return l;
    S res;
    res.lsummin = min(l.lsummin, r.lsummin + l.sum);
    res.rsummin = min(l.rsummin + r.sum, r.rsummin);
    res.sum = l.sum + r.sum;
    res.e = false;
    return res;
}
S e(){ return { 0, 0, 0, true }; }

int main(){
    int N, Q; cin >> N >> Q;
    vector<int> A(N); rep(i,N){ cin >> A[i]; A[i]--; }
    vector<vector<int>> C(N);
    rep(i,N) C[A[i]].push_back(i);
    vector<int> T(N+1);
    T[0] = -1;
    persistent_segtree<S, op, e> pseg(vector<S>(N, { 0, 0, 1, false }));
    rep(i,N){
        T[i+1] = T[i];
        for(int p : C[i]) T[i+1] = pseg.set(T[i+1], p, { 0, 0, -1, false });
    }
    auto satisfy = [&](int l, int r, int a) -> bool {
        if(A[l] < a && A[r-1] < a) return true;
        if(r-l <= 2) return false;
        auto q = pseg.prod(T[a], l, r);
        if(q.lsummin <= -2) return true;
        if(q.rsummin <= -2) return true;
        if(q.lsummin <= -1 && q.rsummin <= -1) return true;
        if(q.sum <= -1) return true;
        return false;
    };
    rep(q, Q){
        int l, r; cin >> l >> r; l--;
        int li = 0, ri = N;
        while(li + 1 < ri){
            int x = (li + ri) / 2;
            (satisfy(l, r, x) ? ri : li) = x;
        }
        cout << ri << '\n';
    }
    return 0;
}



struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0