oj.uz

Submission #766232

# Submission time Handle Problem Language Result Execution time Memory
766232 2023-06-25T11:54:25 Z Valters07 Sequence (APIO23_sequence) C++17
12 / 100
 1260 ms 66892 KB 
#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(int j = 0;j<pos[i].size();j++)
        {
            int posl = pos[i][j];
            auto segl = get1(0,posl-1);
            mil[posl]=segl.fi;
        }
        for(auto x:pos[i])
            upd(x,n,-2,-2);
        for(int j = 0;j<pos[i].size();j++)
        {
            int posl = pos[i][j];
            auto segl = get1(0,posl-1);
            mxl[posl]=segl.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,-2,-2);
    }
    return ans;
}

Compilation message

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

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 5 ms 11988 KB Output is correct
4 Correct 5 ms 12032 KB Output is correct
5 Correct 5 ms 11988 KB Output is correct
6 Incorrect 7 ms 12064 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 5 ms 11988 KB Output is correct
4 Correct 5 ms 12032 KB Output is correct
5 Correct 5 ms 11988 KB Output is correct
6 Incorrect 7 ms 12064 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 955 ms 61116 KB Output is correct
3 Correct 985 ms 61124 KB Output is correct
4 Correct 904 ms 53320 KB Output is correct
5 Correct 981 ms 60172 KB Output is correct
6 Correct 970 ms 60168 KB Output is correct
7 Correct 909 ms 53660 KB Output is correct
8 Incorrect 949 ms 53808 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 1000 ms 53420 KB Output is correct
3 Correct 1052 ms 53296 KB Output is correct
4 Correct 1022 ms 53308 KB Output is correct
5 Correct 1002 ms 53340 KB Output is correct
6 Correct 997 ms 53376 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1260 ms 66892 KB Output is correct
2 Correct 1213 ms 66860 KB Output is correct
3 Correct 1219 ms 66332 KB Output is correct
4 Correct 1237 ms 66380 KB Output is correct
5 Correct 1119 ms 62932 KB Output is correct
6 Incorrect 1119 ms 62928 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 5 ms 11988 KB Output is correct
4 Correct 5 ms 12032 KB Output is correct
5 Correct 5 ms 11988 KB Output is correct
6 Incorrect 7 ms 12064 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 5 ms 11988 KB Output is correct
4 Correct 5 ms 12032 KB Output is correct
5 Correct 5 ms 11988 KB Output is correct
6 Incorrect 7 ms 12064 KB Output isn't correct
7 Halted 0 ms 0 KB -