Submission #760480

#	Time	Username	Problem	Language	Result	Execution time	Memory
760480		wiwiho	Sequence (APIO23_sequence)	C++17	100 / 100	1202 ms	66496 KiB

sequence

#include "sequence.h"

#include <bits/stdc++.h>

using namespace std;

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define iter(a) a.begin(), a.end()
#define pb(a) emplace_back(a)
#define mp(a, b) make_pair(a, b)
#define ff first
#define ss second
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define SZ(a) int(a.size())
#ifdef LOCAL
void debug(){cerr << "\n";}
template<class T, class ... U> void debug(T a, U ... b){cerr << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cerr << *l << " ", l++;
	cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif

typedef long long ll;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.ff << ',' << p.ss << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

#define lc 2 * id
#define rc 2 * id + 1

int n;

struct Node{
    int mn = 0, mx = 0, tag = 0;
};

struct SegTree{
    vector<Node> st;
    SegTree(): st(4 * n) {}
    void addtag(int v, int id){
        st[id].mn += v;
        st[id].mx += v;
        st[id].tag += v;
    }
    void push(int id){
        addtag(st[id].tag, lc);
        addtag(st[id].tag, rc);
        st[id].tag = 0;
    }
    void pull(int id){
        st[id].mn = min(st[lc].mn, st[rc].mn);
        st[id].mx = max(st[lc].mx, st[rc].mx);
    }
    void modify(int l, int r, int v, int L = -1, int R = n - 1, int id = 1){
        if(l <= L && R <= r){
            addtag(v, id);
            return;
        }
        push(id);
        int M = ifloor(L + R, 2);
        if(r <= M) modify(l, r, v, L, M, lc);
        else if(l > M) modify(l, r, v, M + 1, R, rc);
        else{
            modify(l, r, v, L, M, lc);
            modify(l, r, v, M + 1, R, rc);
        }
        pull(id);
    }
    int querymn(int l, int r, int L = -1, int R = n - 1, int id = 1){
        if(l <= L && R <= r) return st[id].mn;
        push(id);
        int M = ifloor(L + R, 2);
        if(r <= M) return querymn(l, r, L, M, lc);
        else if(l > M) return querymn(l, r, M + 1, R, rc);
        else return min(querymn(l, r, L, M, lc), querymn(l, r, M + 1, R, rc));
    }
    int querymx(int l, int r, int L = -1, int R = n - 1, int id = 1){
        if(l <= L && R <= r) return st[id].mx;
        push(id);
        int M = ifloor(L + R, 2);
        if(r <= M) return querymx(l, r, L, M, lc);
        else if(l > M) return querymx(l, r, M + 1, R, rc);
        else return max(querymx(l, r, L, M, lc), querymx(l, r, M + 1, R, rc));
    }
    void _print(int L = -1, int R = n - 1, int id = 1){
        if(L == R){
            cerr << st[id].mn << " ";
            return;
        }
        push(id);
        int M = ifloor(L + R, 2);
        _print(L, M, lc);
        _print(M + 1, R, rc);
    }
    void print(){
        _print();
        cerr << "\n";
    }
};

int lowbit(int x){
    return x & -x;
}

struct BIT{
    vector<int> bit;
    explicit BIT(int sz): bit(sz + 1, INT_MAX) {};
    void modify(int x, int v){
        x++;
        for(; x < SZ(bit); x += lowbit(x)) bit[x] = min(bit[x], v);
    }
    int query(int x){
        x++;
        int ans = INT_MAX;
        for(; x > 0; x -= lowbit(x)) ans = min(ans, bit[x]);
        return ans;
    }
};

struct item{
    int x, y, type, i;
    bool operator<(item b){
        if(x != b.x) return x < b.x;
        if(y != b.y) return y < b.y;
        if(type != b.type) return type < b.type;
        return i < b.i;
    }
};

int sequence(int N, vector<int> A){
    n = N;

    SegTree seg;

    vector<vector<int>> pos(n + 1);
    for(int i = 0; i < n; i++){
        pos[A[i]].pb(i);
        seg.modify(i, n - 1, 1);
    }

    int ans = 0;
    for(int v = 1; v <= n; v++){
        for(int i : pos[v]) seg.modify(i, n - 1, -1);
        //debug("start", v);
        //seg.print();
        
        vector<item> ev;
        vector<int> discr;

        int lst = -1;
        for(int i = 0; i < SZ(pos[v]); i++){
            int j = pos[v][i];
            int nxt = i + 1 == SZ(pos[v]) ? n : pos[v][i + 1];
            {
                int mn = seg.querymn(lst, j - 1);
                int mx = seg.querymx(lst, j - 1);
                int x = i - mx, y = i + mn;
                //debug("left", j, mn, mx, x, y);
                discr.pb(y);
                ev.pb(item({x, y, 0, i}));
            }
            {
                int mn = seg.querymn(j, nxt - 1);
                int mx = seg.querymx(j, nxt - 1);
                int x = i - mn + 1, y = i + mx + 1;
                //debug("right", j, mn, mx, x, y);
                discr.pb(y);
                ev.pb(item({x, y, 1, i}));
            }
            lst = j;
        }

        for(int i : pos[v]) seg.modify(i, n - 1, -1);

        sort(iter(discr));
        uni(discr);
        sort(iter(ev));

        BIT bit(SZ(discr));
        for(auto [x, y, ty, i] : ev){
            //debug("process", x, y, ty, i);
            int id = lower_bound(iter(discr), y) - discr.begin();
            if(ty == 0){
                bit.modify(id, i);
            }
            else{
                int j = bit.query(id);
                if(j == INT_MAX) continue;
                ans = max(ans, i - j + 1);
                //debug("ans", i, j);
            }
        }
    }


    return ans;
}

• 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