oj.uz

Submission #908307

# Submission time Handle Problem Language Result Execution time Memory
908307 2024-01-16T11:02:25 Z winter0101 Sequence (APIO23_sequence) C++17
82 / 100
 2000 ms 74804 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include "sequence.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));
}
};
struct IT{
vector<int>st;
void resz(int n){
st.clear();
st.resize(4*n+9);
}
void update(int id,int l,int r,int u,int val){
if(l>u||r<u)return;
if (l==r){
    st[id]=val;
    return;
}
int mid=(l+r)>>1;
update(id<<1,l,mid,u,val);
update(id<<1|1,mid+1,r,u,val);
st[id]=max(st[id<<1],st[id<<1|1]);
}
int walk(int id,int l,int r,int u,int val){
if (st[id]<val)return -1;
if (l>u)return -1;
if (l==r)return l;
int mid=(l+r)>>1;
int ans=walk(id<<1,l,mid,u,val);
if (ans==-1)return walk(id<<1|1,mid+1,r,u,val);
return ans;
}
};
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==sz(value[i])-1)mx_r[v]=st1.get(1,1,n,v,n)-pf[v],mn_r[v]=st2.get(1,1,n,v,n)-pf[v];
    else mx_r[v]=st1.get(1,1,n,v,value[i][j+1]-1)-pf[v],mn_r[v]=st2.get(1,1,n,v,value[i][j+1]-1)-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,2);
    for1(j,0,sz(value[i])-1){
    int v=value[i][j];
    int suffix=st1.get(1,1,n,v,v);
    if (j==0){
    mx_l[v]=st1.get(1,1,n,1,v)-suffix,mn_l[v]=st2.get(1,1,n,1,v)-suffix;
    }
    else {
    mx_l[v]=st1.get(1,1,n,value[i][j-1]+1,v)-suffix,mn_l[v]=st2.get(1,1,n,value[i][j-1]+1,v)-suffix;
    }
    }
    }
}
struct type{
int id,val;
bool fl;
bool operator < (const type &p){
if (val==p.val)return fl<p.fl;
return val<p.val;
}
};
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();
    IT st;
    for1(i,1,n){
    vector<type>t;
    for1(j,0,sz(value[i])-1){
    int v=value[i][j];
    t.pb({j+1,pf[v]-mx_l[v],0});
    t.pb({j+1,pf[v]+1+mx_r[v],1});
    }
    sort(all(t));
    st.resz(sz(value[i]));
    int m=sz(value[i]);
    for1(j,1,m)st.update(1,1,m,j,-n*10);
    for (auto v:t){
    int id=value[i][v.id-1];
    if (v.fl==0){
    st.update(1,1,m,v.id,pf[id]-mn_l[id]-2*v.id);
    }
    else {
    int pos=st.walk(1,1,m,v.id,pf[id]+1+mn_r[id]-2*v.id-2);
    if (pos!=-1){
    ans=max(ans,v.id-pos+1);
    }
    }
    }
    }
    return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22872 KB Output is correct
2 Correct 6 ms 22872 KB Output is correct
3 Correct 7 ms 22872 KB Output is correct
4 Correct 7 ms 22876 KB Output is correct
5 Correct 7 ms 22876 KB Output is correct
6 Correct 6 ms 22876 KB Output is correct
7 Correct 7 ms 22876 KB Output is correct
8 Correct 7 ms 22876 KB Output is correct
9 Correct 8 ms 22872 KB Output is correct
10 Correct 7 ms 22876 KB Output is correct
11 Correct 7 ms 22872 KB Output is correct
12 Correct 7 ms 22880 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22872 KB Output is correct
2 Correct 6 ms 22872 KB Output is correct
3 Correct 7 ms 22872 KB Output is correct
4 Correct 7 ms 22876 KB Output is correct
5 Correct 7 ms 22876 KB Output is correct
6 Correct 6 ms 22876 KB Output is correct
7 Correct 7 ms 22876 KB Output is correct
8 Correct 7 ms 22876 KB Output is correct
9 Correct 8 ms 22872 KB Output is correct
10 Correct 7 ms 22876 KB Output is correct
11 Correct 7 ms 22872 KB Output is correct
12 Correct 7 ms 22880 KB Output is correct
13 Correct 10 ms 23128 KB Output is correct
14 Correct 12 ms 23132 KB Output is correct
15 Correct 11 ms 23388 KB Output is correct
16 Correct 11 ms 23132 KB Output is correct
17 Correct 9 ms 23128 KB Output is correct
18 Correct 11 ms 23132 KB Output is correct
19 Correct 10 ms 23132 KB Output is correct
20 Correct 11 ms 23132 KB Output is correct
21 Correct 10 ms 23132 KB Output is correct
22 Correct 10 ms 23204 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22872 KB Output is correct
2 Correct 1192 ms 69080 KB Output is correct
3 Correct 1246 ms 69076 KB Output is correct
4 Correct 1205 ms 61360 KB Output is correct
5 Correct 1237 ms 68136 KB Output is correct
6 Correct 1116 ms 68232 KB Output is correct
7 Correct 1049 ms 61876 KB Output is correct
8 Correct 1051 ms 61768 KB Output is correct
9 Correct 1101 ms 61252 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 22872 KB Output is correct
2 Correct 1172 ms 61388 KB Output is correct
3 Correct 1193 ms 61260 KB Output is correct
4 Correct 1153 ms 61260 KB Output is correct
5 Correct 1137 ms 61384 KB Output is correct
6 Correct 1165 ms 61328 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1761 ms 74804 KB Output is correct
2 Correct 1844 ms 74792 KB Output is correct
3 Correct 1809 ms 74224 KB Output is correct
4 Correct 1810 ms 74228 KB Output is correct
5 Correct 1505 ms 70892 KB Output is correct
6 Correct 1446 ms 70896 KB Output is correct
7 Correct 1169 ms 69692 KB Output is correct
8 Correct 1190 ms 69376 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22872 KB Output is correct
2 Correct 6 ms 22872 KB Output is correct
3 Correct 7 ms 22872 KB Output is correct
4 Correct 7 ms 22876 KB Output is correct
5 Correct 7 ms 22876 KB Output is correct
6 Correct 6 ms 22876 KB Output is correct
7 Correct 7 ms 22876 KB Output is correct
8 Correct 7 ms 22876 KB Output is correct
9 Correct 8 ms 22872 KB Output is correct
10 Correct 7 ms 22876 KB Output is correct
11 Correct 7 ms 22872 KB Output is correct
12 Correct 7 ms 22880 KB Output is correct
13 Correct 10 ms 23128 KB Output is correct
14 Correct 12 ms 23132 KB Output is correct
15 Correct 11 ms 23388 KB Output is correct
16 Correct 11 ms 23132 KB Output is correct
17 Correct 9 ms 23128 KB Output is correct
18 Correct 11 ms 23132 KB Output is correct
19 Correct 10 ms 23132 KB Output is correct
20 Correct 11 ms 23132 KB Output is correct
21 Correct 10 ms 23132 KB Output is correct
22 Correct 10 ms 23204 KB Output is correct
23 Correct 258 ms 30212 KB Output is correct
24 Correct 250 ms 30380 KB Output is correct
25 Correct 242 ms 30292 KB Output is correct
26 Correct 265 ms 29448 KB Output is correct
27 Correct 227 ms 29456 KB Output is correct
28 Correct 260 ms 29320 KB Output is correct
29 Correct 186 ms 29264 KB Output is correct
30 Correct 191 ms 29256 KB Output is correct
31 Correct 159 ms 29100 KB Output is correct
32 Correct 159 ms 31296 KB Output is correct
33 Correct 240 ms 30164 KB Output is correct
34 Correct 229 ms 30068 KB Output is correct
35 Correct 258 ms 29984 KB Output is correct
36 Correct 226 ms 30012 KB Output is correct
37 Correct 249 ms 30168 KB Output is correct
38 Correct 255 ms 30292 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 22872 KB Output is correct
2 Correct 6 ms 22872 KB Output is correct
3 Correct 7 ms 22872 KB Output is correct
4 Correct 7 ms 22876 KB Output is correct
5 Correct 7 ms 22876 KB Output is correct
6 Correct 6 ms 22876 KB Output is correct
7 Correct 7 ms 22876 KB Output is correct
8 Correct 7 ms 22876 KB Output is correct
9 Correct 8 ms 22872 KB Output is correct
10 Correct 7 ms 22876 KB Output is correct
11 Correct 7 ms 22872 KB Output is correct
12 Correct 7 ms 22880 KB Output is correct
13 Correct 10 ms 23128 KB Output is correct
14 Correct 12 ms 23132 KB Output is correct
15 Correct 11 ms 23388 KB Output is correct
16 Correct 11 ms 23132 KB Output is correct
17 Correct 9 ms 23128 KB Output is correct
18 Correct 11 ms 23132 KB Output is correct
19 Correct 10 ms 23132 KB Output is correct
20 Correct 11 ms 23132 KB Output is correct
21 Correct 10 ms 23132 KB Output is correct
22 Correct 10 ms 23204 KB Output is correct
23 Correct 1192 ms 69080 KB Output is correct
24 Correct 1246 ms 69076 KB Output is correct
25 Correct 1205 ms 61360 KB Output is correct
26 Correct 1237 ms 68136 KB Output is correct
27 Correct 1116 ms 68232 KB Output is correct
28 Correct 1049 ms 61876 KB Output is correct
29 Correct 1051 ms 61768 KB Output is correct
30 Correct 1101 ms 61252 KB Output is correct
31 Correct 1172 ms 61388 KB Output is correct
32 Correct 1193 ms 61260 KB Output is correct
33 Correct 1153 ms 61260 KB Output is correct
34 Correct 1137 ms 61384 KB Output is correct
35 Correct 1165 ms 61328 KB Output is correct
36 Correct 1761 ms 74804 KB Output is correct
37 Correct 1844 ms 74792 KB Output is correct
38 Correct 1809 ms 74224 KB Output is correct
39 Correct 1810 ms 74228 KB Output is correct
40 Correct 1505 ms 70892 KB Output is correct
41 Correct 1446 ms 70896 KB Output is correct
42 Correct 1169 ms 69692 KB Output is correct
43 Correct 1190 ms 69376 KB Output is correct
44 Correct 258 ms 30212 KB Output is correct
45 Correct 250 ms 30380 KB Output is correct
46 Correct 242 ms 30292 KB Output is correct
47 Correct 265 ms 29448 KB Output is correct
48 Correct 227 ms 29456 KB Output is correct
49 Correct 260 ms 29320 KB Output is correct
50 Correct 186 ms 29264 KB Output is correct
51 Correct 191 ms 29256 KB Output is correct
52 Correct 159 ms 29100 KB Output is correct
53 Correct 159 ms 31296 KB Output is correct
54 Correct 240 ms 30164 KB Output is correct
55 Correct 229 ms 30068 KB Output is correct
56 Correct 258 ms 29984 KB Output is correct
57 Correct 226 ms 30012 KB Output is correct
58 Correct 249 ms 30168 KB Output is correct
59 Correct 255 ms 30292 KB Output is correct
60 Execution timed out 2097 ms 69076 KB Time limit exceeded
61 Halted 0 ms 0 KB -