結果

問題 No.2223 Merged Med
ユーザー 👑 NachiaNachia
提出日時 2023-02-17 23:34:28
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 742 ms / 7,000 ms
コード長 3,883 bytes
コンパイル時間 978 ms
コンパイル使用メモリ 92,284 KB
実行使用メモリ 34,964 KB
最終ジャッジ日時 2024-07-19 14:46:05
合計ジャッジ時間 14,046 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 301 ms
11,028 KB
testcase_14 AC 191 ms
5,376 KB
testcase_15 AC 173 ms
34,328 KB
testcase_16 AC 530 ms
34,264 KB
testcase_17 AC 121 ms
33,596 KB
testcase_18 AC 164 ms
5,376 KB
testcase_19 AC 280 ms
10,944 KB
testcase_20 AC 742 ms
34,396 KB
testcase_21 AC 734 ms
34,396 KB
testcase_22 AC 739 ms
34,400 KB
testcase_23 AC 727 ms
34,400 KB
testcase_24 AC 711 ms
34,528 KB
testcase_25 AC 716 ms
34,528 KB
testcase_26 AC 713 ms
34,396 KB
testcase_27 AC 702 ms
34,400 KB
testcase_28 AC 722 ms
34,396 KB
testcase_29 AC 710 ms
34,396 KB
testcase_30 AC 304 ms
34,884 KB
testcase_31 AC 301 ms
33,856 KB
testcase_32 AC 9 ms
5,376 KB
testcase_33 AC 678 ms
34,400 KB
testcase_34 AC 659 ms
34,964 KB
testcase_35 AC 660 ms
33,728 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 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, { 1, 1, 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 {
        auto q = pseg.prod(T[a], l, r);
        return q.sum - q.rangemax + 1 <= -1 || q.sum <= -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