結果

問題 No.2223 Merged Med
コンテスト
ユーザー Nachia
提出日時 2023-02-17 23:22:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,947 bytes
コンパイル時間 2,233 ms
コンパイル使用メモリ 89,056 KB
最終ジャッジ日時 2025-02-10 18:12:56
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 WA * 27
権限があれば一括ダウンロードができます

ソースコード

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 lsummax, rsummax, rangemax, sum;
    bool e;
};
S op(S l, S r){
    if(l.e) return r;
    if(r.e) return l;
    S res;
    res.lsummax = max(l.lsummax, r.lsummax + l.sum);
    res.rsummax = max(l.rsummax + r.sum, r.rsummax);
    res.rangemax = max({ l.rangemax, r.rangemax, l.rsummax + r.lsummax });
    res.sum = l.sum + r.sum;
    res.e = false;
    return res;
}
S e(){ return { 0, 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, 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, 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);
        return q.sum - q.rangemax <= -1;
    };
    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