oj.uz

Submission #755065

# Submission time Handle Problem Language Result Execution time Memory
755065 2023-06-09T11:23:28 Z IloveN Sequence (APIO23_sequence) C++17
0 / 100
 1148 ms 50132 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]);
    }

    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]);
    }

    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 vr = seg_mx.Get(x, n);
            if (vr >= 0 && vr <= (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 = min(res, j - t + 1);
                }
            }
        }
    }

    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);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < (int)pos[i].size(); ++j) {
            int x = pos[i][j];
            int vr = seg_mx.Get(x, n);
            if (vr >= 0 && vr <= (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 = min(res, j - t + 1);
                }
            }
        }
        for (int x : pos[i]) {
            seg_mx.Update(x, n, -2);
            seg_mn.Update(x, n, -2);
        }
    }
    return res;
}

Subtask #1
0.0 / 11.0

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

Subtask #2
0.0 / 17.0

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

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Incorrect 907 ms 44288 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11988 KB Output is correct
2 Correct 786 ms 36584 KB Output is correct
3 Incorrect 800 ms 36512 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1138 ms 50132 KB Output is correct
2 Correct 1091 ms 50092 KB Output is correct
3 Incorrect 1148 ms 49480 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

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

Subtask #7
0.0 / 18.0

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