oj.uz

Submission #908201

# Submission time Handle Problem Language Result Execution time Memory
908201 2024-01-16T09:28:58 Z winter0101 Sequence (APIO23_sequence) C++17
0 / 100
 2000 ms 78200 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=5e5+9;
struct IT_max{
vector<int>st,lazy;
void resz(int n){
st.clear(),lazy.clear();
st.resize(4*n+9);
lazy.resize(4*n+9);
}
void push(int id){
if (lazy[id]){
    st[id<<1]+=lazy[id];
    st[id<<1|1]+=lazy[id];
    lazy[id<<1]+=lazy[id];
    lazy[id<<1|1]+=lazy[id];
    lazy[id]=0;
}
}
void update(int id,int l,int r,int u,int v,int val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
    st[id]+=val;
    lazy[id]+=val;
    return;
}
push(id);
int mid=(l+r)>>1;
update(id<<1,l,mid,u,v,val);
update(id<<1|1,mid+1,r,u,v,val);
st[id]=max(st[id<<1],st[id<<1|1]);
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return -maxn;
if (u<=l&&r<=v)return st[id];
push(id);
int mid=(l+r)>>1;
return max(get(id<<1,l,mid,u,v),get(id<<1|1,mid+1,r,u,v));
}
};
struct IT_min{
vector<int>st,lazy;
void resz(int n){
st.clear(),lazy.clear();
st.resize(4*n+9);
lazy.resize(4*n+9);
}
void push(int id){
if (lazy[id]){
    st[id<<1]+=lazy[id];
    st[id<<1|1]+=lazy[id];
    lazy[id<<1]+=lazy[id];
    lazy[id<<1|1]+=lazy[id];
    lazy[id]=0;
}
}
void update(int id,int l,int r,int u,int v,int val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
    st[id]+=val;
    lazy[id]+=val;
    return;
}
push(id);
int mid=(l+r)>>1;
update(id<<1,l,mid,u,v,val);
update(id<<1|1,mid+1,r,u,v,val);
st[id]=min(st[id<<1],st[id<<1|1]);
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return maxn;
if (u<=l&&r<=v)return st[id];
push(id);
int mid=(l+r)>>1;
return min(get(id<<1,l,mid,u,v),get(id<<1|1,mid+1,r,u,v));
}
};
int n;
int a[maxn];
vector<int>value[maxn];
int mx_l[maxn],mn_l[maxn],mn_r[maxn],mx_r[maxn];
int pf[maxn];
void pre(){
    IT_max st1;
    IT_min st2;
    st1.resz(n),st2.resz(n);
    auto up=[&](int id,int val){
    st1.update(1,1,n,id,n,val);
    st2.update(1,1,n,id,n,val);
    };
    for1(i,1,n)up(i,-1);
    for1(i,1,n){
    for (auto v:value[i]){
    up(v,2);
    }
    for (auto v:value[i]){
    pf[v]=st1.get(1,1,n,v,v);
    }
    for1(j,0,sz(value[i])-1){
    int v=value[i][j];
    if (j==0)mx_l[v]=st1.get(1,1,n,1,v)-pf[v],mn_l[v]=st2.get(1,1,n,1,v)-pf[v];
    else mx_l[v]=st1.get(1,1,n,value[i][j-1]+1,v)-pf[v],mn_l[v]=st2.get(1,1,n,value[i][j-1]+1,v)-pf[v];
    }
    }
    st1.resz(n),st2.resz(n);
    auto rup=[&](int id,int val){
    st1.update(1,1,n,1,id,val);
    st2.update(1,1,n,1,id,val);
    };
    for1(i,1,n)rup(i,-1);
    for1(i,1,n){
    for (auto v:value[i])rup(v,-1);
    for1(j,0,sz(value[i])-1){
    int v=value[i][j];
    int suffix=st1.get(1,1,n,v,v);
    if (j==sz(value[i])-1){
    mx_r[v]=st1.get(1,1,n,v,n)-suffix,mn_r[v]=st2.get(1,1,n,v,n)-suffix;
    }
    else {
    mx_r[v]=st1.get(1,1,n,v,value[i][j+1]-1)-suffix,mn_r[v]=st2.get(1,1,n,v,value[i][j+1]-1)-suffix;
    }
    }
    }
}
int sequence(int N, std::vector<int> A) {
    n=N;
    for1(i,1,n)a[i]=A[i-1];
    for1(i,1,n)value[a[i]].pb(i);
    int ans=0;
    pre();
    for1(i,1,n){
    for1(x,0,sz(value[i])-1){
    for1(y,0,x){
    int l1=value[i][y],r1=value[i][x];
    int sum=pf[r1]-pf[l1]+1;
    if (sum+mx_l[l1]+mx_r[r1]<0)continue;
    if (sum+mn_l[l1]+mn_r[r1]>x-y+1)continue;
    ans=max(ans,x-y+1);
    }
    }
    }
    return ans;
}
/*signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    int N;
    assert(1 == scanf("%d", &N));

    std::vector<int> A(N);
    for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &A[i]));
    }

    int result = sequence(N, A);
    printf("%d\n", result);
    return 0;
}*/

Subtask #1
0.0 / 11.0

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

Subtask #2
0.0 / 17.0

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

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 22872 KB Output is correct
2 Correct 1231 ms 72560 KB Output is correct
3 Correct 1281 ms 72476 KB Output is correct
4 Execution timed out 2059 ms 62304 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 22876 KB Output is correct
2 Execution timed out 2004 ms 62372 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1639 ms 78200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

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

Subtask #7
0.0 / 18.0

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