Submission #766247

#	Time	Username	Problem	Language	Result	Execution time	Memory
766247		Valters07	Sequence (APIO23_sequence)	C++17	100 / 100	1557 ms	66900 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)};
}
int sequence(int n1, vector<int> a)
{
    n=n1;
    for(int i = 0;i<n;i++)
        pos[a[i]].pb(i+1);
    init();
    for(int i = 1;i<=n;i++)
        upd(i,n,1,1);
    vector<int> mil(n+1), mxl(n+1);
    for(int i = 1;i<=n;i++)
    {
        for(auto x:pos[i])
            mil[x]=get1(0,x-1).fi;
        for(auto x:pos[i])
            upd(x,n,-2,-2);
        for(auto x:pos[i])
            mxl[x]=get1(0,x-1).se;
    }
    init();
    for(int i = 1;i<=n;i++)
        upd(i,n,1,1);
    int ans = 1;
    for(int i = 1;i<=n;i++)
    {
        for(auto x:pos[i])
            upd(x,n,-2,0);
        for(int j = (int)pos[i].size()-ans-1;j>=0;j--)
        {
            int l = pos[i][j];
            while(j+ans<pos[i].size())
            {
                int r = pos[i][j+ans];
                auto segr = get1(r,n);
                int lval = segr.fi-mxl[l], rval = segr.se-mil[l];
                if(lval<=0&&0<=rval)
                    ans++;
                else
                    break;
            }
        }
        for(auto x:pos[i])
            upd(x,n,0,-2);
    }
    return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:110:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |             while(j+ans<pos[i].size())
      |                   ~~~~~^~~~~~~~~~~~~~

• 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