Submission #766196

#	Time	Username	Problem	Language	Result	Execution time	Memory
766196		Valters07	Sequence (APIO23_sequence)	C++17	50 / 100	2094 ms	62796 KiB

sequence

#include <bits/stdc++.h>
#include "sequence.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 5e5+5;
struct node
{
    int c[2], lzy[2];
    node operator +(node t)
    {
        node ret;
        ret.c[0]=min(c[0],t.c[0]);
        ret.c[1]=max(c[1],t.c[1]);
        ret.lzy[0]=ret.lzy[1]=0;
        return ret;
    }
};
vector<int> pos[N];
node segt[4*N];
int n;
void init()
{
    for(int i = 0;i<4*n;i++)
        segt[i]={0,0,0,0};
}
bool cmp(int a, int b)
{
    return a<b;
}
void updlzy(int pos, int siz)
{
    for(int i = 0;i<2;i++)
    {
        int &lzy = segt[pos].lzy[i];
        if(lzy)
        {
            segt[pos].c[i]+=lzy;
            if(siz>1)
                segt[pos*2].lzy[i]+=lzy,
                segt[pos*2+1].lzy[i]+=lzy;
            lzy=0;
        }
    }
}
void upd(int lb, int rb, int val1, int val2, int l = 0, int r = n, int pos = 1)
{
    updlzy(pos,r-l+1);
    if(rb<l||r<lb)
        return;
    if(lb<=l&&r<=rb)
        segt[pos].lzy[0]+=val1,
        segt[pos].lzy[1]+=val2,
        updlzy(pos,r-l+1);
    else
    {
        int mid = (l+r)/2;
        upd(lb,rb,val1,val2,l,mid,pos*2);
        upd(lb,rb,val1,val2,mid+1,r,pos*2+1);
        segt[pos]=segt[pos*2]+segt[pos*2+1];
    }
}
pair<int,int> get1(int lb, int rb, int l = 0, int r = n, int pos = 1)
{
    if(rb<l||r<lb)
        return {1e9,-1e9};
    updlzy(pos,r-l+1);
    if(lb<=l&&r<=rb)
        return {segt[pos].c[0],segt[pos].c[1]};
    int mid = (l+r)/2;
    auto t1 = get1(lb,rb,l,mid,pos*2), t2 = get1(lb,rb,mid+1,r,pos*2+1);
    return {min(t1.fi,t2.fi),max(t1.se,t2.se)};
}
bool check(int n, vector<int> &a, int mid)
{
    init();
    for(int i = 1;i<=n;i++)
        upd(i,n,1,1);
    for(int i = 1;i<=n;i++)
    {
        vector<int> mi, mx;
        for(int j = mid-1;j<pos[i].size();j++)
        {
            int posl = pos[i][j-mid+1];
            auto segl = get1(0,posl-1);
            mi.pb(segl.fi);
        }
        for(int j = 0;j<pos[i].size();j++)
            upd(pos[i][j],n,-2,-2);
        for(int j = mid-1;j<pos[i].size();j++)
        {
            int posl = pos[i][j-mid+1];
            auto segl = get1(0,posl-1);
            mx.pb(segl.se);
        }
        for(int j = 0;j<pos[i].size();j++)
            upd(pos[i][j],n,0,2);
        for(int j = mid-1;j<pos[i].size();j++)
        {
            int ind = j-(mid-1), posr = pos[i][j];
            auto segr = get1(posr,n);
            int l = segr.fi-mx[ind], r = segr.se-mi[ind];
            if(l<=0&&0<=r)
                return 1;
        }
        for(int j = 0;j<pos[i].size();j++)
            upd(pos[i][j],n,0,-2);
    }
    return 0;
}
int sequence(int n1, vector<int> a)
{
    n=n1;
    for(int i = 0;i<n;i++)
        pos[a[i]].pb(i+1);
    int l = 1, r = n;
    while(l<r)
    {
        int mid = (l+r+1)/2;
        if(check(n,a,mid))
            l=mid;
        else
            r=mid-1;
    }
    return l;
}

Compilation message (stderr)

sequence.cpp: In function 'bool check(int, std::vector<int>&, int)':
sequence.cpp:89:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int j = mid-1;j<pos[i].size();j++)
      |                           ~^~~~~~~~~~~~~~
sequence.cpp:95:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for(int j = 0;j<pos[i].size();j++)
      |                       ~^~~~~~~~~~~~~~
sequence.cpp:97:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(int j = mid-1;j<pos[i].size();j++)
      |                           ~^~~~~~~~~~~~~~
sequence.cpp:103:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int j = 0;j<pos[i].size();j++)
      |                       ~^~~~~~~~~~~~~~
sequence.cpp:105:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int j = mid-1;j<pos[i].size();j++)
      |                           ~^~~~~~~~~~~~~~
sequence.cpp:113:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         for(int j = 0;j<pos[i].size();j++)
      |                       ~^~~~~~~~~~~~~~

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