Submission #1060186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060186		alexdd	Sequence (APIO23_sequence)	C++17	100 / 100	1841 ms	68516 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
struct SegTreeLazy_min
{
    int aint[1100000],lazy[1100000];
    void build(int nod, int st, int dr)
    {
        lazy[nod]=0;
        if(st==dr)
        {
            aint[nod]=0;
            return;
        }
        int mij=(st+dr)/2;
        build(nod*2,st,mij);
        aint[nod] = min(aint[nod*2], aint[nod*2+1]);
    }
    void propagate(int nod)
    {
        lazy[nod*2]+=lazy[nod];
        lazy[nod*2+1]+=lazy[nod];
        aint[nod*2]+=lazy[nod];
        aint[nod*2+1]+=lazy[nod];
        lazy[nod]=0;
    }
    void upd(int nod, int st, int dr, int le, int ri, int newv)
    {
        if(le>ri)
            return;
        if(le==st && dr==ri)
        {
            lazy[nod]+=newv;
            aint[nod]+=newv;
            return;
        }
        propagate(nod);
        int mij=(st+dr)/2;
        upd(nod*2,st,mij,le,min(mij,ri),newv);
        upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv);
        aint[nod] = min(aint[nod*2], aint[nod*2+1]);
    }
    int qry(int nod, int st, int dr, int le, int ri)
    {
        if(le>ri)
            return INF;
        if(le==st && dr==ri)
            return aint[nod];
        propagate(nod);
        int mij=(st+dr)/2;
        return min(qry(nod*2,st,mij,le,min(mij,ri)),
                   qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
    }
};
struct SegTreeLazy_max
{
    int aint[1100000],lazy[1100000];
    void build(int nod, int st, int dr)
    {
        lazy[nod]=0;
        if(st==dr)
        {
            aint[nod]=0;
            return;
        }
        int mij=(st+dr)/2;
        build(nod*2,st,mij);
        aint[nod] = max(aint[nod*2], aint[nod*2+1]);
    }
    void propagate(int nod)
    {
        lazy[nod*2]+=lazy[nod];
        lazy[nod*2+1]+=lazy[nod];
        aint[nod*2]+=lazy[nod];
        aint[nod*2+1]+=lazy[nod];
        lazy[nod]=0;
    }
    void upd(int nod, int st, int dr, int le, int ri, int newv)
    {
        if(le>ri)
            return;
        if(le==st && dr==ri)
        {
            lazy[nod]+=newv;
            aint[nod]+=newv;
            return;
        }
        propagate(nod);
        int mij=(st+dr)/2;
        upd(nod*2,st,mij,le,min(mij,ri),newv);
        upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv);
        aint[nod] = max(aint[nod*2], aint[nod*2+1]);
    }
    int qry(int nod, int st, int dr, int le, int ri)
    {
        if(le>ri)
            return -INF;
        if(le==st && dr==ri)
            return aint[nod];
        propagate(nod);
        int mij=(st+dr)/2;
        return max(qry(nod*2,st,mij,le,min(mij,ri)),
                   qry(nod*2+1,mij+1,dr,max(mij+1,le),ri));
    }
};
SegTreeLazy_min aint_plus_min,aint_minus_min;
SegTreeLazy_max aint_plus_max,aint_minus_max;
bool verif(int le, int ri, int cnt0, int N)
{
    if(aint_minus_min.qry(1,0,N,ri,N) > aint_minus_max.qry(1,0,N,0,le-1))
        return 0;
    if(aint_plus_min.qry(1,0,N,0,le-1) > aint_plus_max.qry(1,0,N,ri,N))
        return 0;
    return 1;
}
vector<int> pozs[500005];
int sequence(int N, std::vector<int> A)
{
    for(int i=1;i<=N;i++)
    {
        aint_plus_min.upd(1,0,N,i,N,+1);
        aint_plus_max.upd(1,0,N,i,N,+1);
        aint_minus_min.upd(1,0,N,i,N,+1);
        aint_minus_max.upd(1,0,N,i,N,+1);
        pozs[A[i-1]].push_back(i);
    }
    int mxm=1;
    for(int val=1;val<=N;val++)
    {
        for(auto x:pozs[val])
        {
            aint_plus_min.upd(1,0,N,x,N,-1);
            aint_plus_max.upd(1,0,N,x,N,-1);
            aint_minus_min.upd(1,0,N,x,N,-1);
            aint_minus_max.upd(1,0,N,x,N,-1);

            aint_plus_min.upd(1,0,N,x,N,+1);
            aint_plus_max.upd(1,0,N,x,N,+1);
            aint_minus_min.upd(1,0,N,x,N,-1);
            aint_minus_max.upd(1,0,N,x,N,-1);
        }

        for(int i=0;i<pozs[val].size();i++)
        {
            for(int j=i+mxm;j<pozs[val].size();j++)
            {
                if(verif(pozs[val][i],pozs[val][j],j-i+1,N))
                {
                    mxm = max(mxm, j-i+1);
                }
                else
                    break;
            }
        }

        for(auto x:pozs[val])
        {
            aint_plus_min.upd(1,0,N,x,N,-1);
            aint_plus_max.upd(1,0,N,x,N,-1);
            aint_minus_min.upd(1,0,N,x,N,+1);
            aint_minus_max.upd(1,0,N,x,N,+1);

            aint_plus_min.upd(1,0,N,x,N,-1);
            aint_plus_max.upd(1,0,N,x,N,-1);
            aint_minus_min.upd(1,0,N,x,N,-1);
            aint_minus_max.upd(1,0,N,x,N,-1);
        }
    }
    return mxm;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:144:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         for(int i=0;i<pozs[val].size();i++)
      |                     ~^~~~~~~~~~~~~~~~~
sequence.cpp:146:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |             for(int j=i+mxm;j<pozs[val].size();j++)
      |                             ~^~~~~~~~~~~~~~~~~

• 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