oj.uz

Submission #979475

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

using namespace std;

const int nx=5e5+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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 81 ms 3164 KB Output is correct
14 Correct 79 ms 3408 KB Output is correct
15 Correct 47 ms 3380 KB Output is correct
16 Correct 47 ms 3384 KB Output is correct
17 Incorrect 42 ms 3164 KB Output isn't correct
18 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 2088 ms 353828 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Execution timed out 2085 ms 354396 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 2027 ms 353684 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 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 81 ms 3164 KB Output is correct
14 Correct 79 ms 3408 KB Output is correct
15 Correct 47 ms 3380 KB Output is correct
16 Correct 47 ms 3384 KB Output is correct
17 Incorrect 42 ms 3164 KB Output isn't correct
18 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 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 81 ms 3164 KB Output is correct
14 Correct 79 ms 3408 KB Output is correct
15 Correct 47 ms 3380 KB Output is correct
16 Correct 47 ms 3384 KB Output is correct
17 Incorrect 42 ms 3164 KB Output isn't correct
18 Halted 0 ms 0 KB -