Submission #1181350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181350		adaawf	Sequence (APIO23_sequence)	C++20	100 / 100	1197 ms	135472 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
vector<int> g[500005];
int lazy[2000005], hh = 1e9;
struct MED {
    int x, y;
} t[2000005];
struct SEQ {
    int num, x, y, z, t;
};
bool cmp(SEQ aa, SEQ bb) {
    return aa.x < bb.x;
}
bool cmp2(SEQ aa, SEQ bb) {
    return aa.y < bb.y;
}
MED Merge(MED aa, MED bb) {
    MED res;
    res.x = min(aa.x, bb.x);
    res.y = max(aa.y, bb.y);
    return res;
}
void push(int v) {
    t[v << 1].x += lazy[v];
    t[v << 1].y += lazy[v];
    t[v << 1 | 1].x += lazy[v];
    t[v << 1 | 1].y += lazy[v];
    lazy[v << 1] += lazy[v];
    lazy[v << 1 | 1] += lazy[v];
    lazy[v] = 0;
}
void build(int v, int tl, int tr) {
    lazy[v] = 0;
    if (tl == tr) {
        t[v] = {-tl, -tl};
        return;
    }
    int mid = (tl + tr) >> 1;
    build(v << 1, tl, mid);
    build(v << 1 | 1, mid + 1, tr);
    t[v] = Merge(t[v << 1], t[v << 1 | 1]);
}
void update(int v, int tl, int tr, int l, int r) {
    if (l > r) return;
    if (tl == l && tr == r) {
        t[v].x += 2;
        t[v].y += 2;
        lazy[v] += 2;
        return;
    }
    push(v);
    int mid = (tl + tr) >> 1;
    update(v << 1, tl, mid, l, min(r, mid));
    update(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r);
    t[v] = Merge(t[v << 1], t[v << 1 | 1]);
}
MED sum(int v, int tl, int tr, int l, int r) {
    if (l > r) return {hh, -hh};
    if (tl == l && tr == r) {
        return t[v];
    }
    push(v);
    int mid = (tl + tr) >> 1;
    return Merge(sum(v << 1, tl, mid, l, min(r, mid)), sum(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r));
}
int tt[8000005], lazy2[8000005];
void push2(int v) {
    if (lazy2[v] == hh) return;
    tt[v << 1] = min(tt[v << 1], lazy2[v]);
    tt[v << 1 | 1] = min(tt[v << 1 | 1], lazy2[v]);
    lazy2[v << 1] = min(lazy2[v << 1], lazy2[v]);
    lazy2[v << 1 | 1] = min(lazy2[v << 1 | 1], lazy2[v]);
    lazy2[v] = hh;
}
void update2(int v, int tl, int tr, int l, int r, int x) {
    if (l > r) return;
    if (tl == l && tr == r) {
        tt[v] = min(tt[v], x);
        lazy2[v] = min(lazy2[v], x);
        return;
    }
    push2(v);
    int mid = (tl + tr) >> 1;
    update2(v << 1, tl, mid, l, min(r, mid), x);
    update2(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r, x);
    tt[v] = min(tt[v << 1], tt[v << 1 | 1]);
}
int sum2(int v, int tl, int tr, int l, int r) {
    if (l > r) return hh;
    if (tl == l && tr == r) {
        return tt[v];
    }
    push2(v);
    int mid = (tl + tr) >> 1;
    return min(sum2(v << 1, tl, mid, l, min(r, mid)), sum2(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r));
}
map<int, int> mm;
int z = 0, res = 0, n;
void reset() {
    z = 0;
    for (auto &w : mm) w.second = ++z;
    for (int j = 1; j <= z * 4; j++) {
        tt[j] = hh;
        lazy2[j] = hh;
    }
}
void trya(int i) {
    if (g[i].empty()) return;
    for (int w : g[i]) {
        update(1, 0, n, w, n);
    }
    vector<pair<int, int>> v;
    for (int j = 0; j < g[i].size(); j++) {
        if (j == 0) {
            v.push_back({0, g[i][j] - 1});
        }
        if (j != g[i].size() - 1) {
            v.push_back({g[i][j], g[i][j + 1] - 1});
        }
        else v.push_back({g[i][j], n});
    }
    mm.clear();
    int k = 0;
    vector<SEQ> va, vv;
    for (auto &w : v) {
        auto h = sum(1, 0, n, w.first, w.second);
        mm[h.x] = mm[h.y] = mm[h.x - k] = mm[h.y - k] = 1;
        k += 2;
    }
    reset();
    k = 0;
    for (auto &w : v) {
        auto h = sum(1, 0, n, w.first, w.second);
        int x = mm[h.x], y = mm[h.y], z = mm[h.x - k], t = mm[h.y - k];
        k += 2;
        vv.push_back({k / 2, x, y, z, t});
        va.push_back({k / 2, x, y, z, t});
    }
    sort(va.begin(), va.end(), cmp);
    sort(vv.begin(), vv.end(), cmp2);
    int j = 0;
    for (int i = 0; i < vv.size(); i++) {
        while (j < va.size() && va[j].x <= vv[i].y) {
            update2(1, 1, z, va[j].z, va[j].t, va[j].num);
            j++;
        }
        res = max(res, vv[i].num - sum2(1, 1, z, vv[i].z, vv[i].y));
    }
}
int sequence(int N, vector<int> a) {
    a.push_back(0);
    n = N;
    for (int i = n; i >= 1; i--) a[i] = a[i - 1];
    a[0] = 0;
    for (int i = 1; i <= n; i++) {
        g[a[i]].push_back(i);
    }
    build(1, 0, n);
    for (int i = 1; i <= n; i++) {
        trya(i);
    }
    return res;
}

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 7 / 7
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 22 / 22
• Subtask 7: 18 / 18