제출 #1269996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269996		Faggi	Sequence (APIO23_sequence)	C++20	28 / 100	2097 ms	60140 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,I,D;
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);
    I.resize(0);
    D.resize(0);
    pot=1;
    ll i, j;
    ll ma=0;
    while(pot<(N+1))
        pot*=2;
    seg.resize(pot*2,0);
    I.resize(pot*2);
    D.resize(pot*2);
    for (i = 0; i < sz(A); i++)
    {
        map<ll,ll>ap;
        tam=0;
        for (j = i; j < sz(A); j++)
        {
            update(A[j]+pot,1);
            ap[A[j]]++;
            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]);
            tam++;
        }
        for(j=i; j<sz(A); j++)
            update(A[j]+pot,-1);
    }
    return ma;
}

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