Submission #759316

#	Time	Username	Problem	Language	Result	Execution time	Memory
759316		Luicosas	Sequence (APIO23_sequence)	C++17	100 / 100	957 ms	61084 KiB

sequence

#pragma GCC optimize("Ofast")

#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

#define pb push_back
#define sz(x) (int)(x.size())
#define itr(x) x.begin(), x.end()
#define ref(x) (*(x))
#ifdef LOC
#define debug(...) cerr << #__VA_ARGS__ << " : "; for(auto& dval : {__VA_ARGS__}) cerr << dval << " "; cerr << "\n";
#else 
#define debug(...)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> 
ostream& operator << (ostream& out, vector<T> v) {
    for(auto& i : v) {
        out << i << " ";
    }
    return out;
}

struct node {
    int lb, rb, mn, mx, lazy, lc, rc;
};
ostream& operator << (ostream& out, node v) {
    cout << v.lb << " " << v.rb << " " << v.mn << " " << v.mx << " " << v.lazy << " " << v.lc << " " << v.rc << " ";
    return out;
}

struct segtree {
    vector<node> nodes;

    segtree(int l, int r) {
        nodes.reserve((r - l + 1) * 2);
        build(l, r);
    }

    void build(int l, int r) {
        int idx = sz(nodes);
        nodes.push_back({l, r, l, r, 0, -1, -1});
        
        if(l == r) {
            return;
        }

        int mid = (l + r) / 2;

        nodes[idx].lc = sz(nodes);
        build(l, mid);

        nodes[idx].rc = sz(nodes);
        build(mid + 1, r);
    }

    void sadd(int l, int r, int v, int idx = 0) {
        int lb = nodes[idx].lb, rb = nodes[idx].rb;
        if(r < lb || l > rb) {
            return;
        }
        if(l <= lb && r >= rb) {
            nodes[idx].lazy += v;
            return;
        }

        int lc = nodes[idx].lc, rc = nodes[idx].rc;
        sadd(l, r, v, lc);
        sadd(l, r, v, rc);
        nodes[idx].mx = max(nodes[lc].mx + nodes[lc].lazy, nodes[rc].mx + nodes[rc].lazy);
        nodes[idx].mn = min(nodes[lc].mn + nodes[lc].lazy, nodes[rc].mn + nodes[rc].lazy);
    }
    
    int qrymx(int l, int r, int idx = 0) {
        int lb = nodes[idx].lb, rb = nodes[idx].rb;
        if(r < lb || l > rb) {
            return INT_MIN;
        }
        if(l <= lb && r >= rb) {
            return nodes[idx].mx + nodes[idx].lazy;
        }

        int lc = nodes[idx].lc, rc = nodes[idx].rc, ret = 0;
        ret = max(qrymx(l, r, lc), qrymx(l, r, rc));
        return ret + nodes[idx].lazy;
    }

    int qrymn(int l, int r, int idx = 0) {
        int lb = nodes[idx].lb, rb = nodes[idx].rb;
        if(r < lb || l > rb) {
            return INT_MAX;
        }
        if(l <= lb && r >= rb) {
            return nodes[idx].mn + nodes[idx].lazy;
        }

        int lc = nodes[idx].lc, rc = nodes[idx].rc, ret = 0;
        ret = min(qrymn(l, r, lc), qrymn(l, r, rc));
        return ret + nodes[idx].lazy;
    }
};

int sequence(int N, std::vector<int> A) {
    debug(N); debug(A);

    vector<int> sids(N);
    for(int i = 0; i < N; i++) {
        sids[i] = i;
    }
    sort(sids.begin(), sids.end(), [&](int a, int b) {
        if(A[a] != A[b]) {
            return A[a] < A[b];
        } else {
            return a < b;
        }
    });

    int ptr = 0, mx = 1;
    segtree eqpos(0, N), eqneg(0, N);
    while(ptr < N) {
        for(int i = ptr; i < N && A[sids[i]] == A[sids[ptr]]; i++) {
            eqneg.sadd(sids[i] + 1, N, -2);
        }

        int nptr = ptr;
        while(nptr < N && A[sids[nptr]] == A[sids[ptr]]) {
            if(nptr + mx >= N) {
                return mx;
            }
            int l = sids[nptr], r = sids[nptr + mx];
            if(A[l] != A[r]) {
                nptr++;
                continue;
            }
            if(eqpos.qrymx(r + 1, N) - eqpos.qrymn(0, l) >= 0 && eqneg.qrymn(r + 1, N) - eqneg.qrymx(0, l) <= 0) {
                mx++;
            } else {
                nptr++;
            }
        }
        
        for(; ptr < nptr; ptr++) {
            eqpos.sadd(sids[ptr] + 1, N, -2);
        }
    }
    return mx;
}

• 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