제출 #1270005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270005		Faggi	서열 (APIO23_sequence)	C++20	0 / 100	260 ms	43672 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define fr first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;

vector<ll> seg;
ll pot, tam;

void update(ll nod, ll x)
{
    seg[nod] += x;
    nod /= 2;
    while (nod > 0)
    {
        seg[nod] += x;
        nod /= 2;
    }
}
ll calc(ll x, ll nod, ll act)
{
    if (nod >= pot)
        return nod - pot;
    if (seg[nod * 2] + act >= x)
        return calc(x, nod * 2, act);
    return calc(x, nod * 2 + 1, seg[nod * 2] + act);
}

int sequence(int N, std::vector<int> A)
{
    seg.resize(0);
    pot = 1;
    ll i, j, l, r;
    ll ma = 0;
    while (pot < (N + 1))
        pot *= 2;
    seg.resize(pot * 2, 0);
    ll mid = N - 1;
    for (i = 0; i < N - 1; i++)
    {
        if (A[i] > A[i + 1])
        {
            mid = i;
            break;
        }
    }
    map<ll, ll> ap;
    for (i = 0; i < mid; i++)
    {
        ap[A[i]]++;
        ma = max(ma, ap[A[i]]);
    }
    ap.clear();
    for (i = mid + 1; i < N; i++)
    {
        ap[A[i]]++;
        ma = max(ma, ap[A[i]]);
    }

    ap.clear();
    ap[A[mid]]++;
    tam = 1;
    l = r = mid;
    for (i = mid + 1; i < N; i++)
        if (A[i] == A[mid])
        {
            update(A[i] + pot, 1);
            ap[A[i]]++;
            r = i;
            tam++;
        }
        else
            break;
    for (i = mid - 1; i >= 0; i--)
        if (A[i] == A[mid])
        {
            update(A[i] + pot, 1);
            ap[A[i]]++;
            l = i;
            tam++;
        }
        else
            break;
    ll a = calc((tam / 2) + 1, 1, 0);
    ll b = calc((tam + 1) / 2 + 1, 1, 0);
    ma = max(ma, ap[a]);
    ma = max(ma, ap[b]);
    for (i = A[mid] - 1; i > 0; i--)
    {
        for (j = l - 1; j >= 0; j--)
            if (A[j] == i)
            {
                update(A[j] + pot, 1);
                ap[A[j]]++;
                l = j;
                tam++;
            }
            else
                break;
        for (j = mid + 1; j < N; j++)
            if (A[j] == i)
            {
                update(A[j] + pot, 1);
                ap[A[j]]++;
                r = j;
                tam++;
            }
            else
                break;
        a = calc((tam / 2) + 1, 1, 0);
        b = calc((tam + 1) / 2 + 1, 1, 0);
        ma = max(ma, ap[a]);
        ma = max(ma, ap[b]);
    }
    return ma;
}

• Subtask 1: 0 / 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