Submission #765389

#	Time	Username	Problem	Language	Result	Execution time	Memory
765389		pandapythoner	Sequence (APIO23_sequence)	C++17	100 / 100	1212 ms	111956 KiB

sequence

#include "sequence.h"

#include <bits/stdc++.h>

#include <vector>
using namespace std;

#define ll long long

const ll inf = 1e9;

struct SGT {
    int n;
    vector<ll> mn;
    vector<ll> mx;
    vector<ll> d;

    void apply(int v, ll x) {
        d[v] += x;
                mn[v] += x;
                mx[v] += x;
    }

        void push(int v){
                apply(v + v, d[v]);
                apply(v + v + 1, d[v]);
                d[v] = 0;
        }


        void upd(int v){
                mn[v] = min(mn[v + v], mn[v + v + 1]);
                mx[v] = max(mx[v + v], mx[v + v + 1]);
        }



        void build(int v, int tl, int tr, vector<ll> &a){
                if(tl == tr){
                        mn[v] = a[tl];
                        mx[v] = a[tl];
                        return;
                }
                int tm = (tl + tr) / 2;
                build(v + v, tl, tm, a);
                build(v + v + 1, tm + 1, tr, a);
                upd(v);
        }


        void build(vector<ll> &a){
                n = a.size();
                d.assign(n * 4, 0);
                mn.resize(n * 4);
                mx.resize(n * 4);
                build(1, 0, n - 1, a);
        }


        void add(int v, int tl, int tr, int l, int r, ll x){
                if(tr < l || r < tl){
                        return;
                }
                if(l <= tl && tr <= r){
                        apply(v, x);
                        return;
                }
                int tm = (tl + tr) / 2;
                push(v);
                add(v + v, tl, tm, l, r, x);
                add(v + v + 1, tm + 1, tr, l, r, x);
                upd(v);
        }


        void add(int l, int r, ll x){
                add(1, 0, n - 1, l, r, x);
        }


        pair<ll, ll> get(int v, int tl, int tr, int l, int r){
                if(tr < l || r < tl){
                        return make_pair(inf, -inf);
                }
                if(l <= tl && tr <= r){
                        return make_pair(mn[v], mx[v]);
                }
                int tm = (tl + tr) / 2;
                push(v);
                auto [mn1, mx1] = get(v + v, tl, tm, l, r);
                auto [mn2, mx2] = get(v + v + 1, tm + 1, tr, l, r);
                return make_pair(min(mn1, mn2), max(mx1, mx2));
        }


        pair<ll, ll> get(int l, int r){
                return get(1, 0, n - 1, l, r);
        }
};

int n;
vector<int> a;
SGT sgt;


void solve_rec(vector<array<int, 5>> f, int &rs){
        int m = f.size();
        if(m == 1){
                return;
        }
        int s = m / 2;
        int t = m - s;
        vector<array<int, 5>> fl;
        vector<array<int, 5>> fr;
        for(int i = 0; i < m; i += 1){
                if(i < s){
                        fl.push_back(f[i]);
                } else{
                        fr.push_back(f[i]);
                }
        }
        solve_rec(fl, rs);
        solve_rec(fr, rs);
        int mn = inf;
        int mx = -inf;
        for(int i = 0; i < s; i += 1){
                auto [ps, mnl, mxl, mnr, mxr] = fl[i];
                mnl -= s - i;
                mxl += s - i;
                mn = mnl = min(mn, mnl);
                mx = mxl = max(mx, mxl);
                fl[i] = array<int,5>({ps, mnl, mxl, mnr, mxr});
        }
        mn = inf;
        mx = -inf;
        for(int i = t - 1; i >= 0; i -= 1){
                auto [ps, mnl, mxl, mnr, mxr] = fr[i];
                mnr -= i + 1;
                mxr += i + 1;
                mn = mnr = min(mn, mnr);
                mx = mxr = max(mx, mxr);
                fr[i] = array<int, 5>({ps, mnl, mxl, mnr, mxr});
        }
        int j = 0;
        for(int i = 0; i < t; i += 1){
                auto [psi, mnli, mxli, mnri, mxri] = fr[i];
                while(j < s){
                        auto [psj, mnlj, mxlj, mnrj, mxrj] = fl[j];
                        if(mnlj <= mxri && mnri <= mxlj){
                                break;
                        }
                        j += 1;
                }
                if(j == s){
                        break;
                }
                rs = max(rs, i + 1 + (s - j));
        }
}


int sequence(int N, std::vector<int> A) {
        n = N;
        a = A;
        vector<ll> sgt_init(n + 1);
        for(int i = 0; i <= n; i += 1){
                sgt_init[i] = i;
        }
        sgt.build(sgt_init);
        map<int, vector<int>> mp;
        for(int i = 0; i < n; i += 1){
                mp[a[i]].push_back(i);
        }
        int rs = 1;
        for(auto [x, pss]: mp){
                vector<array<int, 5>> f;
                for(auto i: pss){
                        sgt.add(i + 1, n, -1);
                }
                for(auto i: pss){
                        auto [lmn, lmx] = sgt.get(0, i);
                        auto [rmn, rmx] = sgt.get(i + 1, n);
                        f.push_back(array<int, 5>({i, lmn, lmx, rmn, rmx}));
                }
                solve_rec(f, rs);
                for(auto i: pss){
                        sgt.add(i + 1, n, -1);
                }
        }
    return rs;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:183:55: warning: narrowing conversion of 'lmn' from 'std::tuple_element<0, std::pair<long long int, long long int> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
  183 |                         f.push_back(array<int, 5>({i, lmn, lmx, rmn, rmx}));
      |                                                       ^~~
sequence.cpp:183:60: warning: narrowing conversion of 'lmx' from 'std::tuple_element<1, std::pair<long long int, long long int> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
  183 |                         f.push_back(array<int, 5>({i, lmn, lmx, rmn, rmx}));
      |                                                            ^~~
sequence.cpp:183:65: warning: narrowing conversion of 'rmn' from 'std::tuple_element<0, std::pair<long long int, long long int> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
  183 |                         f.push_back(array<int, 5>({i, lmn, lmx, rmn, rmx}));
      |                                                                 ^~~
sequence.cpp:183:70: warning: narrowing conversion of 'rmx' from 'std::tuple_element<1, std::pair<long long int, long long int> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
  183 |                         f.push_back(array<int, 5>({i, lmn, lmx, rmn, rmx}));
      |                                                                      ^~~

• 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