Submission #749688

#	Time	Username	Problem	Language	Result	Execution time	Memory
749688		eyalz	Sequence (APIO23_sequence)	C++17	28 / 100	2074 ms	51160 KiB

sequence

#include "sequence.h"

#pragma GCC diagnostic ignored "-Wliteral-suffix"
#pragma GCC target "tbm,abm,bmi,bmi2"
#include <bits/stdc++.h>
using namespace std;
#define inlineexpr inline constexpr
#define gcd std::__gcd
#define bitsizeof(x) (CHAR_BIT*sizeof(x))

/*
#include <ext/random>
auto seed = chrono::steady_clock::now().time_since_epoch().count();
using rnggen = __gnu_cxx::sfmt216091_64;
*/

inlineexpr int ctoi(const char c, const int radix)
{
    return
        ('0' <= c && c <= '9')?(c-'0'):
        ('A' <= c && c <= 'Z')?(c-'A'+10):
        ('a' <= c && c <= 'z')?(c-'a'+10):
        0;
}

template<class T, const char... P>
inlineexpr T stoN()
{
    constexpr char p[] = {P...,'\0'};
    constexpr size_t s = sizeof...(P);
    constexpr bool sign = p[0] == '-';
    constexpr bool has_sign = (p[0] == '-' || p[0] == '+');
    constexpr bool has_special_radix = p[has_sign] == '0';
    constexpr size_t radix_idx = has_sign+has_special_radix;
    constexpr int radix =
        !has_special_radix?10:
        (p[radix_idx] == 'b')?2:
        (p[radix_idx] == 'x')?16:
        8;
    constexpr bool has_letter_radix = ((radix==2)||(radix==16));
    constexpr size_t digit_start_idx = radix_idx + has_letter_radix;

    T res = 0;
    size_t i = digit_start_idx;
    if(i >= s)return 0;

    for(;i<s;++i)
        res = radix*res + ctoi(p[i],radix);

    return (sign?-1:1) * res;
}

using i8 = signed char;
using u8 = unsigned char;
using i16 = short;
using u16 = unsigned short;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;

inlineexpr i8 operator ""i8(unsigned long long x){return i8(x);}
inlineexpr u8 operator ""u8(unsigned long long x){return u8(x);}
inlineexpr i16 operator ""i16(unsigned long long x){return i16(x);}
inlineexpr u16 operator ""u16(unsigned long long x){return u16(x);}
inlineexpr i32 operator ""i32(unsigned long long x){return i32(x);}
inlineexpr u32 operator ""u32(unsigned long long x){return u32(x);}
inlineexpr i64 operator ""i64(unsigned long long x){return i64(x);}
inlineexpr u64 operator ""u64(unsigned long long x){return u64(x);}

#define DEFINE_LITERAL(type, name) template<char... P> inlineexpr type operator"" name(){return stoN<type,P...>();}

DEFINE_LITERAL(i128, i128)
DEFINE_LITERAL(i128, lll)
DEFINE_LITERAL(i128, LLL)
DEFINE_LITERAL(u128, u128)
DEFINE_LITERAL(u128, ulll)
DEFINE_LITERAL(u128, ULLL)

using f32 = float;
using f64 = double;
using f80 = __float80;
using fex = long double;
using f128 = __float128;

using decimal32 = float __attribute__((mode(SD)));
using d32 = decimal32;
using decimal64 = float __attribute__((mode(DD)));
using d64 = decimal64;
using decimal128 = float __attribute__((mode(TD)));
using d128 = decimal128;

inlineexpr f32 operator ""f32(long double x){return f32(x);}
inlineexpr f64 operator ""f64(long double x){return f64(x);}
inlineexpr f80 operator ""f80(long double x){return f80(x);}
inlineexpr fex operator ""fex(long double x){return fex(x);}
inlineexpr f128 operator ""f128(long double x){return f128(x);}

inlineexpr d32 operator ""d32(long double x){return d32(x);}
inlineexpr d64 operator ""d64(long double x){return d64(x);}
inlineexpr d128 operator ""d128(long double x){return d128(x);}

template<class T> inlineexpr T condneg(T x, bool n){return x^-n;}
template<class T> inlineexpr make_unsigned_t<T> unsign(T x){return x;}
template<class T> inlineexpr T urs(T x, int d){return unsign(x)>>d;}
inlineexpr i32 log2(i32 x){return __builtin_ia32_bsrsi(x);}
inlineexpr i32 log2(i64 x){return __builtin_ia32_bsrdi(x);}
template<class T> inlineexpr i32 clog2(T x){return log2(x-1)+1;}
inlineexpr u16 c16(u8 hi, u8 lo){return (u16(hi)<<8)+lo;}
inlineexpr u32 c32(u16 hi, u16 lo){return (u32(hi)<<16)+lo;}
inlineexpr u64 c64(u32 hi, u32 lo){return (u64(hi)<<32)+lo;}
inlineexpr u128 c128(u64 hi, u64 lo){return (u128(hi)<<64)+lo;}
inlineexpr u8 lo(u16 x){return u8(x);}
inlineexpr u16 lo(u32 x){return u16(x);}
inlineexpr u32 lo(u64 x){return u32(x);}
inlineexpr u64 lo(u128 x){return u64(x);}
inlineexpr u8 hi(u16 x){return u8(x>>8);}
inlineexpr u16 hi(u32 x){return u16(x>>16);}
inlineexpr u32 hi(u64 x){return u32(x>>32);}
inlineexpr u64 hi(u128 x){return u64(x>>64);}
inlineexpr i32 poc(u32 x){return __builtin_popcount(x);}
inlineexpr i32 poc(i32 x){return __builtin_popcount(x);}
inlineexpr i32 poc(u64 x){return __builtin_popcountll(x);}
inlineexpr i32 poc(i64 x){return __builtin_popcountll(x);}
inlineexpr i32 poc(u128 x){return __builtin_popcountll(lo(x))+__builtin_popcountll(hi(x));}
inlineexpr i32 clz(u16 x){return __builtin_ia32_lzcnt_u16(x);}
inlineexpr i32 clz(i16 x){return __builtin_ia32_lzcnt_u16(x);}
inlineexpr i32 clz(u32 x){return __builtin_clz(x);}
inlineexpr i32 clz(i32 x){return __builtin_clz(x);}
inlineexpr i32 clz(u64 x){return __builtin_clzll(x);}
inlineexpr i32 clz(i64 x){return __builtin_clzll(x);}
inlineexpr i32 ctz(u16 x){return __builtin_ia32_tzcnt_u16(x);}
inlineexpr i32 ctz(i16 x){return __builtin_ia32_tzcnt_u16(x);}
inlineexpr i32 ctz(u32 x){return __builtin_ctz(x);}
inlineexpr i32 ctz(i32 x){return __builtin_ctz(x);}
inlineexpr i32 ctz(u64 x){return __builtin_ctzll(x);}
inlineexpr i32 ctz(i64 x){return __builtin_ctzll(x);}
template<class T> inlineexpr i32 clo(T x){return clz(~x);}
template<class T> inlineexpr i32 cto(T x){return ctz(~x);}
template<class T> inlineexpr T mask_bit(int d){return T(1)<<d;}
template<class T> inlineexpr T mask_low(int d){return mask_bit<T>(d)-1;}
template<class T> inlineexpr T mask_high(int d){return ~mask_low<T>(bitsizeof(T)-d);}
template<class T> inlineexpr T mask_between(int s, int e){return mask_low<T>(e)&~mask_low<T>(s);}
template<class T> inlineexpr T isolate_mask(T x, T m){return x&m;}
template<class T> inlineexpr T zero_mask(T x, T m){return x&~m;}
template<class T> inlineexpr T one_mask(T x, T m){return x|m;}
template<class T> inlineexpr T flip_mask(T x, T m){return x^m;}
template<class T> inlineexpr T set_mask(T x, T m, bool v){return x^((-v^x)&m);}
inlineexpr u32 extract_mask(u32 x, u32 m){return __builtin_ia32_pext_si(x,m);}
inlineexpr u64 extract_mask(u64 x, u64 m){return __builtin_ia32_pext_di(x,m);}
inlineexpr u32 deposit_mask(u32 x, u32 m){return __builtin_ia32_pdep_si(x,m);}
inlineexpr u64 deposit_mask(u64 x, u64 m){return __builtin_ia32_pdep_di(x,m);}
template<class T> inlineexpr T ror(T x, int d){return urs(x,d)|(x<<(bitsizeof(x)-d));}
template<class T> inlineexpr T rol(T x, int d){return (x<<d)|urs(x,bitsizeof(x)-d);}
template<class T> inlineexpr T btt(T x, int d){return !!isolate_mask(x,mask_bit<T>(d));}
template<class T> inlineexpr T lsb(T x){return x&-x;}
template<class T> inlineexpr T msb(T x){return T(1)<<log2(x);}
template<class T> inlineexpr T lepow2(T x){return msb(x);}
template<class T> inlineexpr T ltpow2(T x){return lepow2(x-1);}
template<class T> inlineexpr T gepow2(T x){return T(1)<<clog2(x);}
template<class T> inlineexpr T gtpow2(T x){return gepow2(x+1);}
template<class T> inlineexpr bool ispow2(T x){return !(x-lsb(x));}
template<class T, int s = bitsizeof(T), T mask = T(~0)>
struct RBIT{static T result(T x)
{
    const int _s = s >> 1;
    const T _mask = mask ^ T(mask << _s);
    x = ((x&~_mask) >> _s)|((x&_mask) << _s);
    return RBIT<T,_s,_mask>::result(x);
}};
template<class T, T mask> struct RBIT<T,1,mask>{static T result(T x){return x;}};
template<class T> constexpr T rbit(T x){return RBIT<make_unsigned_t<T>>::result(x);}


#ifdef LOCAL
    #define DEBUG 1
    #define ifdbg_(x) x
    #define ifndbg_(x)
#else
    #define DEBUG 0
    #define ifdbg_(x)
    #define ifndbg_(x) x
#endif

#define ifdbg if(DEBUG)
#define ifndbg if(!DEBUG)

#define dbginfo ifdbg_("at "<<__func__<<" line "<<__LINE__)
#define dbgloc ifdbg cdbg<<dbginfo<<nl
#define dbg ifdbg cdbg<<dbginfo<<":\t"<<

ostream cdbg(0);

constexpr char nl = '\n';
constexpr char sp = ' ';
constexpr char eq = '=';
constexpr char cm = ',';

#define dammit throw runtime_error("bruh moment");

#define ff first
#define ss second
#define sf second.first
#define tt second.second

#define pub push_back
#define pob pop_back
#define emb emplace_back
#define ety empty()
#define ins insert
#define ers erase
#define sz size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define lobd lower_bound
#define upbd upper_bound

template<int D, class T>
struct tensor : public vector<tensor<D-1,T>>
{
    using base = vector<tensor<D-1,T>>;
    template<class U, class... Args>
    constexpr tensor(U n = U(), Args... args) : base(n,tensor<D-1,T>(args...)){}
    constexpr size_t size(int dim = 0)const{return (dim == 0)?base::size():(*this)[0].size(dim-1);}
};
template<class T>
struct tensor<1,T> : public vector<T>
{
    using base = vector<T>;
    template<class... Args>
    constexpr tensor(Args... args) : base(args...){}
    constexpr tensor(initializer_list<T> args) : base(args){}
    constexpr size_t size(int dim = 0)const{return base::size();}
};

template<class T>
struct revit
{
    T& v;
    revit(T &_v):v(_v){}
    constexpr auto begin()const{return std::rbegin(v);}
    constexpr auto cbegin()const{return std::crbegin(v);}
    constexpr auto end()const{return std::rend(v);}
    constexpr auto cend()const{return std::crend(v);}
    constexpr auto rbegin()const{return std::begin(v);}
    constexpr auto crbegin()const{return std::cbegin(v);}
    constexpr auto rend()const{return std::end(v);}
    constexpr auto crend()const{return std::cend(v);}
};

template<class Cmp>
struct compinv
{
    template<class T, class U>
    inline constexpr bool operator()(const T& lhs, const U& rhs)const{return Cmp()(rhs,lhs);}
};

template<class T, class Cmp>
struct pqueue : std::priority_queue<T,vector<T>,compinv<Cmp>>
{
    bool remove(const T& value)
    {
        auto it = find(this->c.begin(), this->c.end(), value);
        if(it == this->c.end())return false;
        if(it == this->c.begin())this->pop();
        else
        {
            this->c.erase(it);
            make_heap(this->c.begin(), this->c.end(), this->comp);
        }
        return true;
    }
};

template<class T>
using vec = vector<T>;
template<class T>
using vvec = vec<vec<T>>;
template<class T, class Cmp>
using pq = pqueue<T,Cmp>;
template<class T>
using pqmin = pqueue<T,less<T>>;
template<class T>
using pqmax = pqueue<T,greater<T>>;

using uint = u32;
using lint = i64;
using ulint = u64;
using llint = i128;
using ullint = u128;
using dloat = fex;
using ii = pair<int,int>;
using iii = pair<int,ii>;
using ll = pair<lint,lint>;
using vi = vec<int>;
using vvi = vvec<int>;
using vii = vec<ii>;
using vvii = vvec<ii>;
using vb = vec<bool>;
using vvb = vvec<bool>;
using vl = vec<lint>;
using dijk = pqmin<ii>;
using str = string;
using vc = vec<char>;

constexpr dloat EPS = 1e-9;

#define ifn(x) if(!(x))
#define elif else if
#define elifn else ifn
#define whilen(x) while(!(x))

#define fori(i,e,n) for(int i=e;i<n;++i)
#define forie(i,e,n) for(int i=e;i<=n;++i)
#define forir(i,e,n) for(int i=e;i>n;--i)
#define forier(i,e,n) for(int i=e;i>=n;--i)
#define forl(i,e,n) for(lint i=e;i<n;++i)
#define forle(i,e,n) for(lint i=e;i<=n;++i)
#define forlr(i,e,n) for(lint i=e;i>n;--i)
#define forler(i,e,n) for(lint i=e;i>=n;--i)
#define forea(a,v) for(auto &a:v)
#define forea2(a,a2,v) for(auto &[a,a2]:v)
#define forear(a,v) forea(a,revit(v))
#define forea2r(a,a2,v) forea2(a,a2,revit(v))
#define forit(it,v) for(auto it=v.begin();it!=v.end();++it)
#define foritr(it,v) for(auto it=v.rbegin();it!=v.rend();++it)

template<class T, class E>
istream& operator>>(istream& is, pair<T,E>& h){return is>>h.ff>>h.ss;}
template<class T>
istream& operator>>(istream& is, vec<T>& h){forea(t,h)is>>t;return is;}

template<class T, class E>
ostream& operator<<(ostream& os, const pair<T,E>& h){return os<<h.ff<<'-'<<h.ss;}
template<class T>
ostream& operator<<(ostream& os, const vec<T>& h){forea(t,h)os<<t<<sp;return os;}
template<class T>
ostream& operator<<(ostream& os, const vvec<T>& h){forea(t,h)os<<t<<nl;return os;}
template<class T>
ostream& operator<<(ostream& os, const queue<T>& h){forea(t,h)os<<t<<sp;return os;}
template<class T>
ostream& operator<<(ostream& os, const deque<T>& h){forea(t,h)os<<t<<sp;return os;}
template<class T>
ostream& operator<<(ostream& os, const set<T>& h){forea(t,h)os<<t<<sp;return os;}
template<class T, class U>
ostream& operator<<(ostream& os, const map<T,U>& h){forea2(t,u,h)os<<t<<" = "<<u<<nl;return os;}

constexpr lint MOD = 1e9+7;
constexpr lint MOD2 = 1e9+9;

struct mint
{
    lint m,x;
    constexpr mint():m(MOD),x(0){}
    constexpr mint(lint _x):m(MOD),x((_x+m)%m){}
    constexpr mint(lint _x, lint _m):m(_m),x((_x+m)%m){}

    template<class U> inlineexpr operator U()const{return x;}
    inlineexpr bool operator!()const{return !x;}

    inline friend ostream& operator<<(ostream& os, const mint& h){return os<<h.x;}
    inline friend istream& operator>>(istream& is, mint& h){is>>h.x;h=mint(h.x,h.m);return is;}

    inlineexpr mint operator+()const{return *this;}
    inlineexpr mint operator-()const{return mint(-x,m);}

    template<class U> inlineexpr mint operator+(const U& h)const{return mint(x+lint(h),m);}
    template<class U> inlineexpr mint operator-(const U& h)const{return *this+-h;}
    template<class U> inlineexpr mint operator*(const U& h)const{return mint(x*lint(h),m);}
    template<class U> constexpr mint operator^(const U& h)const{U p=h;mint r(1,m),a(x,m);for(;p;p>>=1){if(p&1)r*=a;a*=a;}return r;}

    constexpr mint operator~()const{return *this^(m-2);}

    template<class U> inlineexpr bool operator==(const U& h)const{return x==lint(h);}
    template<class U> inlineexpr bool operator!=(const U& h)const{return !(*this==h);}

    template<class U> inlineexpr mint& operator+=(const U& h){return *this=*this+h;}
    template<class U> inlineexpr mint& operator-=(const U& h){return *this+=-h;}
    template<class U> inlineexpr mint& operator*=(const U& h){return *this=*this*h;}
    template<class U> constexpr mint& operator^=(const U& h){return *this=*this^h;}
};
inlineexpr mint operator ""m(unsigned long long x){return mint(x);}

#define fastio cin.tie(0)->sync_with_stdio(0);
#define setdbg ifdbg cdbg.rdbuf(cerr.rdbuf());
#define cinfail ifdbg cin.exceptions(cin.failbit);

vi AA;

vi merge(const vi& r, const vi& l)
{
    vi arr;
    int li = 0, ri = 0;
    while(li < l.size() || ri < r.size())
    {
        if(li >= l.size())
        {
            for(;ri < r.size();++ri)
            {
                arr.pub(r[ri]);
            }
        }
        elif(ri >= r.size())
        {
            for(;li < l.size();++li)
            {
                arr.pub(l[li]);
            }
        }
        else
        {
            if(l[li] < r[ri])
            {
                arr.pub(l[li]);
                ++li;
            }
            else
            {
                arr.pub(r[ri]);
                ++ri;
            }
        }
    }
    return move(arr);
}

struct stree
{
    stree *l = nullptr, *r = nullptr;
    int lb,rb;
    stree(int _lb, int _rb):lb(_lb),rb(_rb)
    {
        if(lb == rb)
        {
            return;
        }
        int mb = (lb+rb)/2;
        l = new stree(lb,mb);
        r = new stree(mb+1,rb);

    }

    vector<int> sort_range(int _lb, int _rb) const
    {
        if(rb < _lb || _rb < lb) return {};
        if(_lb <= lb && rb <= _rb)
        {
            vector<int> res;
            fori(i,lb,rb+1)res.pub(AA[i]);
            sort(all(res));
            return move(res);
        }
        vector<int> lv = l->sort_range(_lb,_rb);
        vector<int> rv = r->sort_range(_lb,_rb);
        return merge(lv,rv);
    }

    int query(int _lb, int _rb) const
    {
        vector<int> sorted = sort_range(_lb, _rb);
        int mid1 = sorted[sorted.size()/2];
        int mid2 = sorted[(sorted.size()-1)/2];
        return max(count(all(sorted),mid1),count(all(sorted),mid2));
    }
};

int sequence(int N, vi A)
{
    #ifdef EVAL
    cerr.rdbuf(0);
    #endif // EVAL

    AA = move(A);

    /*stree t(0,N-1);
    int res = -1;
    fori(i,0,N)
    {
        fori(j,i,N)
        {
            int h = t.query(i,j);
            cerr << i << ' ' << j << ' ' << h << '\n';
            if(h > res)res = h;
        }
    }

    return res;*/

    int res = -1;

    fori(i,0,N)
    {
        set<ii> s;
        map<int,int> co;
        //vector<int> co(N,0);
        s.insert({AA[i],i});
        co[AA[i]] = 1;

        //cerr << "set: " << s << "\nmap\n" << co << nl;

        auto it = s.begin();
        auto it2 = it;

        //cerr << "current " << *it << sp << *it2 << nl;

        int curr = 1;

        if(curr > res) res = curr;

        fori(j,i+1,N)
        {
            //cerr << "i " << i << " j " << j << nl;

            ii newthing = {AA[j],j};
            //cerr << "adding " << newthing << nl;
            s.insert(newthing);
            ++co[AA[j]];
            //cerr << "set: " << s << "\nmap\n" << co << nl;
            if(it == it2)
            {
                if(newthing < *it)--it;
                else ++it2;
            }
            else
            {
                if(newthing < *it)--it2;
                elif(*it2 < newthing) ++it;
                else
                {
                    --it2;++it;
                }
            }
            //cerr << "current " << *it << sp << *it2 << nl;
            curr = max(co[it->first],co[it2->first]);
            if(curr > res) res = curr;
            //cerr << "res is " << res << nl;
        }
    }
    return res;
}

Compilation message (stderr)

sequence.cpp: In function 'vi merge(const vi&, const vi&)':
sequence.cpp:396:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  396 |     while(li < l.size() || ri < r.size())
      |           ~~~^~~~~~~~~~
sequence.cpp:396:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  396 |     while(li < l.size() || ri < r.size())
      |                            ~~~^~~~~~~~~~
sequence.cpp:398:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  398 |         if(li >= l.size())
      |            ~~~^~~~~~~~~~~
sequence.cpp:400:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  400 |             for(;ri < r.size();++ri)
      |                  ~~~^~~~~~~~~~
sequence.cpp:405:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  405 |         elif(ri >= r.size())
      |              ~~~^~~~~~~~~~~
sequence.cpp:407:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  407 |             for(;li < l.size();++li)
      |                  ~~~^~~~~~~~~~
sequence.cpp:426:16: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
  426 |     return move(arr);
      |            ~~~~^~~~~
sequence.cpp:426:16: note: remove 'std::move' call
sequence.cpp: In member function 'std::vector<int> stree::sort_range(int, int) const':
sequence.cpp:453:24: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
  453 |             return move(res);
      |                    ~~~~^~~~~
sequence.cpp:453:24: note: remove 'std::move' call

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