제출 #984644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
984644		efishel	서열 (APIO23_sequence)	C++17	31 / 100	2023 ms	74320 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;

#define mid ((l+r)>>1)
#define off (2*(mid-l+1))
struct SegTree {
    struct Node {
        ll minP, maxP, minS, maxS, sum;

        Node (ll val): minP(val), maxP(val), minS(val), maxS(val), sum(val) {}

        Node operator+ (const Node &o) const {
            Node ans(0);
            ans.minP = min(minP, sum+o.minP);
            ans.maxP = max(maxP, sum+o.maxP);
            ans.minS = min(o.sum+minS, o.minS);
            ans.maxS = max(o.sum+maxS, o.maxS);
            ans.sum = sum+o.sum;
            return ans;
        };
    };

    vector <Node> tree;
    ll n;

    SegTree (ll n): tree(2*n, Node(0)), n(n) {}

    void update (ll at, ll val) { update(at, val, 0, n-1, 0); }
    void update (ll at, ll val, ll l, ll r, ll id) {
        if (at <= l && r <= at) {
            tree[id] = Node(val);
            return;
        }
        if (at <= mid)
            update(at, val, l, mid, id+1);
        else
            update(at, val, mid+1, r, id+off);
        tree[id] = tree[id+1] + tree[id+off];
    }

    Node query (ll ql, ll qr) { return query(ql, qr, 0, n-1, 0) + Node(0); }
    Node query (ll ql, ll qr, ll l, ll r, ll id) {
        if (qr < l || r < ql) return Node(0);
        if (ql <= l && r <= qr) return tree[id];
        return query(ql, qr, l, mid, id+1) + query(ql, qr, mid+1, r, id+off);
    }
};

int sequence (int n, vi ve) {
    for (int &i : ve) i--;
    vll idxs[n]{};
    for (ll i = 0; i < n; i++) idxs[ve[i]].push_back(i);
    ll ans = 0;
    SegTree st(n);
    for (ll i = 0; i < n; i++) {
        st.update(i, 1);
    }
    cerr << boolalpha;
    for (ll i = 0; i < n; i++) {
        for (ll j : idxs[i]) st.update(j, 0);
        ll l = 0, r = idxs[i].size();
        while (l+1 < r) {
            ll midd = (l+r)>>1;
            bool val = false;
            for (ll k = midd; k < idxs[i].size(); k++) {
                ll sum = st.query(idxs[i][k-midd], idxs[i][k]).sum;
                if (sum < 0) {
                    ll raise = st.query(0, idxs[i][k-midd]-1).maxS + st.query(idxs[i][k]+1, n-1).maxP;
                    sum += raise;
                    val |= sum >= -(midd+1);
                } else {
                    ll drop = st.query(0, idxs[i][k-midd]-1).minS + st.query(idxs[i][k]+1, n-1).minP;
                    sum += drop;
                    val |= sum <= (midd+1);
                }
            }
            if (val) {
                l = midd;
            } else {
                r = midd;
            }
        }
        ans = max(ans, l+1);
        for (ll j : idxs[i]) st.update(j, -1);
    }
    return int(ans);
}

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'int sequence(int, vi)':
sequence.cpp:69:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for (ll k = midd; k < idxs[i].size(); k++) {
      |                               ~~^~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 17
• Subtask 3: 7 / 7
• Subtask 4: 0 / 12
• Subtask 5: 13 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18