제출 #1311902

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311902		M_SH_O	서열 (APIO23_sequence)	C++20	11 / 100	2096 ms	6016 KiB

sequence

/*#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")*/
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
#define ll long long
#define ll1 long long
#define ull unsigned long long
#define dou long double
#define str string
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll, ll>
#define vpll vector<pair<ll, ll>>
#define vbool vector<bool>
#define vstr vector<str>
#define vvll vector<vll>
#define pb push_back
#define pf push_front
#define endl "\n"
#define fr first
#define se second
// #define sortcmp(a) sort(a.begin(), a.end(), cmp)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;
//using namespace __gnu_pbds;

const ll INF = 1e18+7;
const int lg = 20;
//const ll MOD = 1e9+7;
const ll MOD2 = 998244353;

mt19937 rng(1488);
ll randll(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}

struct ed {
    ll pref, suff, sum;
};

vector<ed> tree;

void bt(ll v, ll tl, ll tr) {
    if (tl == tr) {
        tree[v] = {0, 0, -1};
        return;
    }
    ll tm = (tl+tr)/2;

    bt(v*2, tl, tm);
    bt(v*2+1, tm+1, tr);

    tree[v].pref = max(tree[v*2].pref, tree[v*2].sum+tree[v*2+1].pref);
    tree[v].suff = max(tree[v*2+1].suff, tree[v*2+1].sum+tree[v*2].suff);
    tree[v].sum = tree[v*2+1].sum + tree[v*2].sum;
}

void upd(ll idx, ll val, ll v, ll tl, ll tr) {
    if (tl == tr) {
        tree[v] = {max((ll)0, val), max((ll)0, val), val};
        return;
    }

    ll tm = (tl+tr)/2;

    if (idx <= tm) upd(idx, val, v*2, tl, tm);
    else upd(idx, val, v*2+1, tm+1, tr);

    tree[v].pref = max(tree[v*2].pref, tree[v*2].sum+tree[v*2+1].pref);
    tree[v].suff = max(tree[v*2+1].suff, tree[v*2+1].sum+tree[v*2].suff);
    tree[v].sum = tree[v*2+1].sum + tree[v*2].sum;
}

ed get(ll l, ll r, ll v, ll tl, ll tr) {
    //cout << "! " << tl << ' ' << tr << endl;
    if (l <= tl && tr <= r) {
        return tree[v];
    }

    if (tl > r || tr < l) return {0, 0, 0};

    ll tm = (tl+tr)/2;
    ed p = get(l, r, v*2, tl, tm), p1 = get(l, r, v*2+1, tm+1, tr), res;

    res.pref = max(p.pref, p.sum+p1.pref);
    res.suff = max(p1.suff, p1.sum+p.suff);
    res.sum = p1.sum + p.sum;
    return res;
}

vll tree1;

ll get_min(ll l, ll r, ll v, ll tl, ll tr) {
    if (l <= tl && tr <= r) return tree1[v];
    if (tl > r || tr < l) return INF;

    ll tm = (tl+tr)/2;
    //push(v, tl, tr);
    ll p = get_min(l, r, v*2, tl, tm), p1 = get_min(l, r, v*2+1, tm+1, tr);
    return min(p,p1);
}


void update(ll idx, ll val, ll v, ll tl, ll tr) {

    if (tl == tr) {
        if (val == INF) tree1[v] = val;
        else tree1[v] = min(tree1[v], val);
        return;
    }

    ll tm = (tl+tr)/2;

    if (idx <= tm)update(idx, val, v*2, tl, tm);
    else update(idx, val, v*2+1, tm+1, tr);

    tree1[v] = min(tree1[v*2], tree1[v*2+1]);
}

int sequence1(int n, vi a) {
    tree.clear();
    tree.resize(n*4+7);
    tree1.clear();
    tree1.resize(n*8+7, INF);
    vvll v(n+7);
    for (int i = 0; i < n; i ++) {
        v[a[i]].pb(i);
    }
    bt(1, 0, n-1);

    ll maxl = 0;
    for (int i = 1; i <= n; i ++) {
        for (int j : v[i]) {
            upd(j, 1, 1, 0, n-1);
        }
        ll last = -1, k = 0;
        vll v1;
        for (int j : v[i]) {
            //cout << last+1 << ' ' << j << endl;
            ed p = get(last+1, j, 1, 0, n-1);
            ll pref = get(0, j, 1, 0, n-1).sum;
            update(pref - p.suff + n, k, 1, 0, n*2);
            v1.pb(pref - p.suff + n);
            //cout << pref - p.suff << ' ' << pref << ' ';

            ll x = n-1;
            if (k+1 < v[i].size()) x = v[i][k+1]-1;
            ll p1 = get(j, x, 1, 0, n-1).pref-1;

            //cout << p1 << endl;

            ll res = k-get_min(0, pref+p1+n, 1, 0, 2*n)+1;
            //cout << k << ' ' << get_min(0, pref+p1+n, 1, 0, 2*n) << endl;
            //cout << endl;
            maxl = max(maxl, res);

            last = j;
            k ++;
        }

        for (int j : v1) {
            update(j, INF, 1, 0, n*2);
        }

    }

    return maxl;
}

int sequence(int n, vi a) {
    ll maxl = 0;
    for (int i = 0; i < n; i ++) {
        vll b;
        map<ll, ll> m;
        for (int j = i; j < n; j ++) {
            b.pb(a[j]);
            m[a[j]] ++;
            sort(b);
            ll x = (b.size()-1)/2, x1 = x+(b.size()-1)%2;
            maxl = max({maxl, m[b[x]], m[b[x1]]});
        }
    }

    return maxl;
}

/*int main() {
    speed;
    srand(time(0));

    cout << solve(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2});
}*/

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