Submission #874586

#	Time	Username	Problem	Language	Result	Execution time	Memory
874586		Stickfish	Sequence (APIO23_sequence)	C++17	100 / 100	902 ms	46932 KiB

sequence

#include "sequence.h"
#include <iostream>
#include <vector>
using namespace std;

inline bool in(pair<int, int> sg, int x) {
    return sg.first <= x && x <= sg.second;
}

inline bool intersect(pair<int, int> sg1, pair<int, int> sg2) {
    return in(sg1, sg2.first) || in(sg2, sg1.first);
}

inline int distance(pair<int, int> sg1, pair<int, int> sg2) {
    if (intersect(sg1, sg2))
        return 0;
    if (sg1.first > sg2.first)
        return sg1.first - sg2.second;
    return sg2.first - sg1.second;
}

int get_ans(vector<pair<int, int>> a) {
    int n = a.size();
    vector<pair<int, int>> cova(n);
    cova[n - 1].first = a[n - 1].first - (n - 1);
    cova[n - 1].second = a[n - 1].second + (n - 1);
    for (int i = n - 2; i >= 0; --i) {
        cova[i].first = min(cova[i + 1].first, a[i].first - i);
        cova[i].second = max(cova[i + 1].second, a[i].second + i);
    }
    int ans = 0;
    for (int l = 0; l < n; ++l) {
        int lb = l + ans;
        int ub = n;
        while (ub - lb > 1) {
            int mb = (lb + ub) / 2;
            pair<int, int> sg = cova[mb];
            sg.first += l;
            sg.second -= l;
            //cout << l << ' ' << r << ": " << "(" << sg.first << ' ' << sg.second << ") " << 
            if (intersect(a[l], sg)) {
                lb = mb;
            } else {
                ub = mb;
            }
        }
        ans = lb - l;
    }
    return ans;
}

struct stree {
    void resize(int n) {
        sz = n;
        mod.resize(2 * n);
        mn.resize(2 * n);
        mx.resize(2 * n);
    }

    void add(int l, int r, int x) {
        //cout << "OHOH " << l << ' ' << r << endl;;
        //for (int i = l; i < r; ++i)
            //mod[i] += x;
        //return;
        add(0, 0, sz, l, r, x);
    }

    int get_min(int l, int r) {
        //cout << "HOHO " << l << ' ' << r << endl;;
        //int ans = 1000000;
        //for (int i = l; i < r; ++i)
            //ans = min(ans, mod[i]);
        //return ans;
        return get_min(0, 0, sz, l, r);
    }

    int get_max(int l, int r) {
        //cout << "HAHA " << l << ' ' << r << endl;;
        //int ans = -1000000;
        //for (int i = l; i < r; ++i)
            //ans = max(ans, mod[i]);
        //return ans;
        return get_max(0, 0, sz, l, r);
    }

 private:
     int sz;
     vector<int> mod;
     vector<int> mn;
     vector<int> mx;

     void add(int ind, int lnd, int rnd, int l, int r, int x) {
         if (l <= lnd && rnd <= r) {
             mod[ind] += x;
             mn[ind] += x;
             mx[ind] += x;
             return;
         }
         if (lnd >= r || l >= rnd)
             return;
         int mnd = (lnd + rnd) / 2;
         int chd = ind + (mnd - lnd) * 2;
         add(ind + 1, lnd, mnd, l, r, x);
         add(chd, mnd, rnd, l, r, x);
         mn[ind] = min(mn[ind + 1], mn[chd]) + mod[ind];
         mx[ind] = max(mx[ind + 1], mx[chd]) + mod[ind];
     }

     int get_max(int ind, int lnd, int rnd, int l, int r) {
         if (l <= lnd && rnd <= r) {
             return mx[ind];
         }
         if (lnd >= r || l >= rnd)
             return -10000000;
         int mnd = (lnd + rnd) / 2;
         int chd = ind + (mnd - lnd) * 2;
         return max(get_max(ind + 1, lnd, mnd, l, r), get_max(chd, mnd, rnd, l, r)) + mod[ind];
     }

     int get_min(int ind, int lnd, int rnd, int l, int r) {
         if (l <= lnd && rnd <= r) {
             return mn[ind];
         }
         if (lnd >= r || l >= rnd)
             return 10000000;
         int mnd = (lnd + rnd) / 2;
         int chd = ind + (mnd - lnd) * 2;
         return min(get_min(ind + 1, lnd, mnd, l, r), get_min(chd, mnd, rnd, l, r)) + mod[ind];
     }
};

int sequence(int N, vector<int> A) {
    vector<vector<int>> ra(N + 1);
    for (int i = 0; i < N; ++i) {
        ra[A[i]].push_back(i);
    }
    stree tr;
    tr.resize(N);
    for (int i = 0; i < N; ++i) {
        tr.add(i, N, 1);
    }
    int ans = 0;
    for (int x = 1; x <= N; ++x) {
        if (ra[x].empty())
            continue;

        //vector<pair<int, int>> p;
        //int pval = 0;
        //int cpmx = 0;
        //int cpmn = 0;
        //for (int i = 0; i < N; ++i) {
            //if (A[i] == x) {
                //p.push_back({cpmn, cpmx});
                //cpmx = cpmn = pval;
            //} else if (A[i] < x) {
                //--pval;
                //cpmn = min(cpmn, pval);
            //} else {
                //++pval;
                //cpmx = max(cpmx, pval);
            //}
        //}
        //p.push_back({cpmn, cpmx});
        
        for (auto i : ra[x])
            tr.add(i, N, -1);
        vector<pair<int, int>> p;

        ra[x].insert(ra[x].begin(), 0);
        ra[x].push_back(N - 1);
        //for (int i = 0; i < N; ++i)
            //cout << tr.get_min(i, i + 1) << ' ';
        //cout << endl;
        for (size_t i = 0; i + 1 < ra[x].size(); ++i) {
            int l = ra[x][i];
            int r = ra[x][i + 1] + 1;
            p.push_back({tr.get_min(l, r), tr.get_max(l, r)});
        }
        ra[x].pop_back();
        ra[x].erase(ra[x].begin());

        p[0].first = min(p[0].first, 0);
        p[0].second = max(p[0].second, 0);
        //cout << x << ": ";
        //for (auto x : p)
            //cout << "(" << x.first << ' ' << x.second << ") ";
        //cout << get_ans(p) << endl;
        ans = max(ans, get_ans(p));
        for (auto i : ra[x])
            tr.add(i, N, -1);
    }
    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