Submission #979499

#	Time	Username	Problem	Language	Result	Execution time	Memory
979499		12345678	Sequence (APIO23_sequence)	C++17	28 / 100	149 ms	11632 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=2e3+5;

int n, a[nx], res;

struct persist
{
    struct node
    {
        int f;
        node *l, *r;
        node(int f): f(f), l(0), r(0){} 
    };
    typedef node* pnode;
    pnode rt[nx];
    void build(int l, int r, pnode &k)
    {
        k=new node(0);
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, k->l);
        build(md+1, r, k->r);
    }
    void update(int l, int r, pnode &k, pnode t, int idx)
    {
        k=new node(*t);
        if (l==r) return k->f++, void();
        int md=(l+r)/2;
        if (idx<=md) update(l, md, k->l, t->l, idx);
        else update(md+1, r, k->r, t->r, idx);
        k->f=k->l->f+k->r->f;
    }
    int query(int l, int r, pnode k, pnode t, int key)
    {
        if (l==r) return k->f-t->f;
        int md=(l+r)/2;
        if ((k->l->f-t->l->f)>=key) return query(l, md, k->l, t->l, key);
        else return query(md+1, r, k->r, t->r, key-(k->l->f-t->l->f));
    }
} s;

int sequence(int N, std::vector<int> A) {
    n=N;
    for (int i=1; i<=n; i++) a[i]=A[i-1];
    s.build(1, n, s.rt[0]);
    for (int i=1; i<=n; i++) s.update(1, n, s.rt[i], s.rt[i-1], a[i]);
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=i; j++)
        {
            if ((i-j+1)%2) res=max(res, s.query(1, n, s.rt[i], s.rt[j-1], ((i-j+2)/2)));
            else res=max({res, s.query(1, n, s.rt[i], s.rt[j-1], (i-j+1)/2), s.query(1, n, s.rt[i], s.rt[j-1], (i-j+1)/2+1)});
        }
    }
    return res;
}

• 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