oj.uz

Submission #979474

# Submission time Handle Problem Language Result Execution time Memory
979474 2024-05-11T05:37:19 Z 12345678 Sequence (APIO23_sequence) C++17
0 / 100
 2000 ms 380612 KB 
#include "sequence.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;

int n, a[nx], res, t;
map<int, int> mp;

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], mp[a[i]]=0;
    for (auto &[x, y]:mp) y=++t;
    s.build(1, n, s.rt[0]);
    for (int i=1; i<=n; i++) a[i]=mp[a[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)});
            //cout<<"debug "<<i<<' '<<j<<' '<<res<<'\n';
        }
    }
    //cout<<"debug "<<s.query(1, n, 1, s.rt[8], s.rt[0], 4)<<'\n';
    //cout<<"debug "<<s.query(1, n, 1, s.rt[8], s.rt[0], 5)<<'\n';
    return res;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2408 KB Output is correct
5 Incorrect 1 ms 2392 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2408 KB Output is correct
5 Incorrect 1 ms 2392 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Execution timed out 2067 ms 372036 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Execution timed out 2070 ms 355632 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 380612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2408 KB Output is correct
5 Incorrect 1 ms 2392 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2408 KB Output is correct
5 Incorrect 1 ms 2392 KB Output isn't correct
6 Halted 0 ms 0 KB -