oj.uz

Submission #755089

# Submission time Handle Problem Language Result Execution time Memory
755089 2023-06-09T11:43:41 Z IloveN Sequence (APIO23_sequence) C++17
31 / 100
 873 ms 50012 KB 
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(), vr.end()

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;

const int N = 5e5 + 10;

struct segment_tree_max
{
    int it[N * 4], lazy[N * 4], n, u, v, x;

	int combine(int obj1, int obj2) { return max(obj1, obj2);}

    void build(int id, int l, int r)
    {
        if (l == r)
        {
            it[id] = 0;
            lazy[id] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build((id << 1) | 1, mid + 1, r);
        it[id] = combine(it[id << 1], it[(id << 1) | 1]);
        lazy[id] = 0;
    }

    void init(int len)
    {
        n = len;
        build(1, 1, n);
    }

    void apply(int id, int val)
    {
        it[id] += val;
        lazy[id] += val;
    }

    void push(int id)
    {
        apply(id << 1, lazy[id]);
        apply((id << 1) | 1, lazy[id]);
        lazy[id] = 0;
    }

    void update(int id, int l, int r)
    {
        if (l > v || r < u) return;
        if (u <= l && r <= v)
        {
            apply(id, x);
            return;
        }
        int mid = (l + r) >> 1;
        push(id);
        update(id << 1, l, mid);
        update((id << 1) | 1, mid + 1, r);
        it[id] = combine(it[id << 1], it[(id << 1) | 1]);
    }

    int get(int id, int l, int r)
    {
        if (l > v || r < u) return -1e9;
        if (u <= l && r <= v) return it[id];
        int mid = (l + r) >> 1;
        push(id);
        return combine(get(id << 1, l, mid), get((id << 1) | 1, mid + 1, r));
    }

    int lw(int id, int l, int r)
    {
        if (l > v || r < u || it[id] < x) return -1;
        if (l == r) return l;
        int mid = (l + r) >> 1;
        push(id);
        int tmp = lw(id << 1, l, mid);
        if (tmp != -1) return tmp;
        return lw((id << 1) | 1, mid + 1, r);
    }

    void Update(int l, int r, int val)
    {
        u = l;
        v = r;
        x = val;
        update(1, 1, n);
    }

    int Get(int l, int r)
    {
        u = l;
        v = r;
        if (l > r) return 0;
        return get(1, 1, n);
    }

    int Lower_bound(int l, int r, int val)
    {
        u = l;
        v = r;
        x = val;
        return lw(1, 1, n);
    }
} seg_mx;

struct segment_tree_min
{
    int it[N * 4], lazy[N * 4], n, u, v, x;

	int combine(int obj1, int obj2) { return min(obj1, obj2);}

    void build(int id, int l, int r)
    {
        if (l == r)
        {
            it[id] = 0;
            lazy[id] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build((id << 1) | 1, mid + 1, r);
        it[id] = combine(it[id << 1], it[(id << 1) | 1]);
        lazy[id] = 0;
    }

    void init(int len)
    {
        n = len;
        build(1, 1, n);
    }

    void apply(int id, int val)
    {
        it[id] += val;
        lazy[id] += val;
    }

    void push(int id)
    {
        apply(id << 1, lazy[id]);
        apply((id << 1) | 1, lazy[id]);
        lazy[id] = 0;
    }

    void update(int id, int l, int r)
    {
        if (l > v || r < u) return;
        if (u <= l && r <= v)
        {
            apply(id, x);
            return;
        }
        int mid = (l + r) >> 1;
        push(id);
        update(id << 1, l, mid);
        update((id << 1) | 1, mid + 1, r);
        it[id] = combine(it[id << 1], it[(id << 1) | 1]);
    }

    int get(int id, int l, int r)
    {
        if (l > v || r < u) return 1e9;
        if (u <= l && r <= v) return it[id];
        int mid = (l + r) >> 1;
        push(id);
        return combine(get(id << 1, l, mid), get((id << 1) | 1, mid + 1, r));
    }

    int lw(int id, int l, int r)
    {
        if (l > v || r < u || it[id] > x) return -1;
        if (l == r) return l;
        int mid = (l + r) >> 1;
        push(id);
        int tmp = lw(id << 1, l, mid);
        if (tmp != -1) return tmp;
        return lw((id << 1) | 1, mid + 1, r);
    }

    void Update(int l, int r, int val)
    {
        u = l;
        v = r;
        x = val;
        update(1, 1, n);
    }

    int Get(int l, int r)
    {
        u = l;
        v = r;
        if (l > r) return 0;
        return get(1, 1, n);
    }

    int Lower_bound(int l, int r, int val)
    {
        u = l;
        v = r;
        x = val;
        return lw(1, 1, n);
    }
} seg_mn;

int a[N];
vi pos[N];

int sequence(int n, vi arr) {
    for (int i = 1; i <= n; ++i) a[i] = arr[i - 1];
    for (int i = 1; i <= n; ++i) pos[i].clear();
    for (int i = 1; i <= n; ++i) pos[a[i]].eb(i);
    seg_mx.init(n);
    seg_mn.init(n);
    for (int i = 1; i <= n; ++i) {
        seg_mx.Update(i, n, -1);
        seg_mn.Update(i, n, -1);
    }
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int x : pos[i]) {
            seg_mx.Update(x, n, 2);
            seg_mn.Update(x, n, 2);
        }
        for (int j = 0; j < (int)pos[i].size(); ++j) {
            int x = pos[i][j];
            int vl = seg_mx.Get(x, x);
            int vr = seg_mx.Get(x, n);
            if (vr >= 0 && vl <= (j + 1) * 2) res = max(res, j + 1);
            else if (vr < 0) {
                int l = seg_mn.Lower_bound(1, x - 1, vr);
                if (l != -1) {
                    int t = upper_bound(all(pos[i]), l) - pos[i].begin();
                    res = max(res, j - t + 1);
                }
            }
            else if (vr >= 0 && vl > (j + 1) * 2) {
                vr = seg_mn.Get(x, n);
                if (vr <= (j + 1) * 2) res = max(res, j + 1);
                else {
                    int l = seg_mx.Lower_bound(1, x - 1, vr - (j + 1) * 2);
                    if (l != -1) {
                        int t = upper_bound(all(pos[i]), l) - pos[i].begin();
                        res = max(res, j - t + 1);
                    }
                }
            }
        }
    }
    return res;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12044 KB Output is correct
2 Correct 7 ms 12000 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 12088 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 6 ms 12028 KB Output is correct
11 Correct 8 ms 11988 KB Output is correct
12 Correct 7 ms 12092 KB Output is correct

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12044 KB Output is correct
2 Correct 7 ms 12000 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 12088 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 6 ms 12028 KB Output is correct
11 Correct 8 ms 11988 KB Output is correct
12 Correct 7 ms 12092 KB Output is correct
13 Correct 10 ms 12116 KB Output is correct
14 Correct 10 ms 12116 KB Output is correct
15 Correct 8 ms 12116 KB Output is correct
16 Correct 10 ms 12116 KB Output is correct
17 Correct 8 ms 12116 KB Output is correct
18 Correct 9 ms 12116 KB Output is correct
19 Correct 8 ms 12156 KB Output is correct
20 Correct 9 ms 12116 KB Output is correct
21 Incorrect 9 ms 12200 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12044 KB Output is correct
2 Correct 577 ms 44288 KB Output is correct
3 Correct 615 ms 44276 KB Output is correct
4 Correct 610 ms 36448 KB Output is correct
5 Correct 601 ms 43344 KB Output is correct
6 Correct 546 ms 43340 KB Output is correct
7 Correct 510 ms 36812 KB Output is correct
8 Correct 558 ms 37052 KB Output is correct
9 Correct 494 ms 36560 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12000 KB Output is correct
2 Correct 550 ms 36588 KB Output is correct
3 Correct 564 ms 36456 KB Output is correct
4 Correct 556 ms 36524 KB Output is correct
5 Correct 511 ms 36580 KB Output is correct
6 Incorrect 525 ms 36536 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 830 ms 50012 KB Output is correct
2 Correct 862 ms 50000 KB Output is correct
3 Correct 873 ms 49428 KB Output is correct
4 Correct 843 ms 49360 KB Output is correct
5 Correct 713 ms 46028 KB Output is correct
6 Correct 712 ms 46004 KB Output is correct
7 Correct 611 ms 44984 KB Output is correct
8 Correct 619 ms 44584 KB Output is correct

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12044 KB Output is correct
2 Correct 7 ms 12000 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 12088 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 6 ms 12028 KB Output is correct
11 Correct 8 ms 11988 KB Output is correct
12 Correct 7 ms 12092 KB Output is correct
13 Correct 10 ms 12116 KB Output is correct
14 Correct 10 ms 12116 KB Output is correct
15 Correct 8 ms 12116 KB Output is correct
16 Correct 10 ms 12116 KB Output is correct
17 Correct 8 ms 12116 KB Output is correct
18 Correct 9 ms 12116 KB Output is correct
19 Correct 8 ms 12156 KB Output is correct
20 Correct 9 ms 12116 KB Output is correct
21 Incorrect 9 ms 12200 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12044 KB Output is correct
2 Correct 7 ms 12000 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 7 ms 12088 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 7 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 6 ms 12028 KB Output is correct
11 Correct 8 ms 11988 KB Output is correct
12 Correct 7 ms 12092 KB Output is correct
13 Correct 10 ms 12116 KB Output is correct
14 Correct 10 ms 12116 KB Output is correct
15 Correct 8 ms 12116 KB Output is correct
16 Correct 10 ms 12116 KB Output is correct
17 Correct 8 ms 12116 KB Output is correct
18 Correct 9 ms 12116 KB Output is correct
19 Correct 8 ms 12156 KB Output is correct
20 Correct 9 ms 12116 KB Output is correct
21 Incorrect 9 ms 12200 KB Output isn't correct
22 Halted 0 ms 0 KB -