Submission #1059913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059913		alexdd	Sequence (APIO23_sequence)	C++17	41 / 100	2087 ms	67156 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, int paritate)
    {
        lazy[nod]=0;
        if(st==dr)
        {
            if(st%2==paritate) aint[nod]=0;
            else aint[nod]=INF;
            return;
        }
        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, int paritate)
    {
        lazy[nod]=0;
        if(st==dr)
        {
            if(st%2==paritate) aint[nod]=0;
            else aint[nod]=-INF;
            return;
        }
        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_min[2];
SegTreeLazy_max aint_max[2];
bool verif(int le1, int ri1, int le2, int ri2, int cnt0, int N)
{
    pair<int,int> x[2],y[2];
    for(int i=0;i<2;i++)
    {
        x[i] = {aint_min[i].qry(1,0,N,le1,ri1), aint_max[i].qry(1,0,N,le1,ri1)};
        y[i] = {aint_min[i].qry(1,0,N,le2,ri2), aint_max[i].qry(1,0,N,le2,ri2)};
    }

    for(int p=0;p<2;p++)
    {
        for(int q=0;q<2;q++)
        {
            pair<int,int> a = x[p], b = y[q];
            if(a.first > b.first)
                swap(a,b);
            if(p==q)
            {
                if(a.second + cnt0 - 1 >= b.first)
                    return 1;
            }
            else
            {
                if(a.second + cnt0 >= b.first)
                    return 1;
            }
        }
    }
    return 0;
}
vector<int> pozs[500005];
int sequence(int N, std::vector<int> A)
{
    aint_min[0].build(1,0,N,0);
    aint_min[1].build(1,0,N,1);
    aint_max[0].build(1,0,N,0);
    aint_max[1].build(1,0,N,1);
    for(int i=1;i<=N;i++)
    {
        aint_min[0].upd(1,0,N,i,N,+1);
        aint_min[1].upd(1,0,N,i,N,+1);
        aint_max[0].upd(1,0,N,i,N,+1);
        aint_max[1].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_min[0].upd(1,0,N,x,N,-1);
            aint_min[1].upd(1,0,N,x,N,-1);
            aint_max[0].upd(1,0,N,x,N,-1);
            aint_max[1].upd(1,0,N,x,N,-1);
        }

        for(int i=0;i<pozs[val].size();i++)
        {
            for(int j=i;j<pozs[val].size();j++)
            {
                /*for(int k=0;k<pozs[val].size();k++)
                {
                    int x = pozs[val][k];
                    if(k<i)
                    {
                        aint_min[0].upd(1,0,N,x,pozs[val][i]-1,-1);
                        aint_min[1].upd(1,0,N,x,pozs[val][i]-1,-1);
                        aint_max[0].upd(1,0,N,x,pozs[val][i]-1,+1);
                        aint_max[1].upd(1,0,N,x,pozs[val][i]-1,+1);
                    }
                    else if(k>j)
                    {
                        aint_min[0].upd(1,0,N,x,N,-1);
                        aint_min[1].upd(1,0,N,x,N,-1);
                        aint_max[0].upd(1,0,N,x,N,+1);
                        aint_max[1].upd(1,0,N,x,N,+1);
                    }
                }*/

                if(verif(0,pozs[val][i]-1,pozs[val][j],N,j-i+1,N))
                {
                    mxm = max(mxm, j-i+1);
                }

                /*for(int k=0;k<pozs[val].size();k++)
                {
                    int x = pozs[val][k];
                    if(k<i)
                    {
                        aint_min[0].upd(1,0,N,x,pozs[val][i]-1,+1);
                        aint_min[1].upd(1,0,N,x,pozs[val][i]-1,+1);
                        aint_max[0].upd(1,0,N,x,pozs[val][i]-1,-1);
                        aint_max[1].upd(1,0,N,x,pozs[val][i]-1,-1);
                    }
                    else if(k>j)
                    {
                        aint_min[0].upd(1,0,N,x,N,+1);
                        aint_min[1].upd(1,0,N,x,N,+1);
                        aint_max[0].upd(1,0,N,x,N,-1);
                        aint_max[1].upd(1,0,N,x,N,-1);
                    }
                }*/
            }
        }

        for(auto x:pozs[val])
        {
            aint_min[0].upd(1,0,N,x,N,-1);
            aint_min[1].upd(1,0,N,x,N,-1);
            aint_max[0].upd(1,0,N,x,N,-1);
            aint_max[1].upd(1,0,N,x,N,-1);
        }
    }
    return mxm;
}

Compilation message (stderr)

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

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