oj.uz

Submission #908318

# Submission time Handle Problem Language Result Execution time Memory
908318 2024-01-16T11:06:33 Z winter0101 Sequence (APIO23_sequence) C++17
82 / 100
 2000 ms 84752 KB 
#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{
int st[maxn*4],lazy[maxn*4];
void resz(int n){
for1(i,1,4*n)st[i]=lazy[i]=0;
}
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{
int st[maxn*4],lazy[maxn*4];
void resz(int n){
for1(i,1,4*n)st[i]=lazy[i]=0;
}
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,4*m)st.st[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 24 ms 54096 KB Output is correct
2 Correct 23 ms 54108 KB Output is correct
3 Correct 26 ms 54124 KB Output is correct
4 Correct 25 ms 54104 KB Output is correct
5 Correct 27 ms 54108 KB Output is correct
6 Correct 22 ms 54108 KB Output is correct
7 Correct 23 ms 54108 KB Output is correct
8 Correct 25 ms 54108 KB Output is correct
9 Correct 24 ms 54096 KB Output is correct
10 Correct 23 ms 54104 KB Output is correct
11 Correct 23 ms 54148 KB Output is correct
12 Correct 24 ms 54108 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 54096 KB Output is correct
2 Correct 23 ms 54108 KB Output is correct
3 Correct 26 ms 54124 KB Output is correct
4 Correct 25 ms 54104 KB Output is correct
5 Correct 27 ms 54108 KB Output is correct
6 Correct 22 ms 54108 KB Output is correct
7 Correct 23 ms 54108 KB Output is correct
8 Correct 25 ms 54108 KB Output is correct
9 Correct 24 ms 54096 KB Output is correct
10 Correct 23 ms 54104 KB Output is correct
11 Correct 23 ms 54148 KB Output is correct
12 Correct 24 ms 54108 KB Output is correct
13 Correct 28 ms 54356 KB Output is correct
14 Correct 29 ms 54316 KB Output is correct
15 Correct 28 ms 54364 KB Output is correct
16 Correct 27 ms 54364 KB Output is correct
17 Correct 29 ms 54372 KB Output is correct
18 Correct 31 ms 54240 KB Output is correct
19 Correct 27 ms 54364 KB Output is correct
20 Correct 26 ms 54364 KB Output is correct
21 Correct 27 ms 54360 KB Output is correct
22 Correct 28 ms 54352 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 54096 KB Output is correct
2 Correct 980 ms 69116 KB Output is correct
3 Correct 1032 ms 68980 KB Output is correct
4 Correct 1026 ms 68792 KB Output is correct
5 Correct 1033 ms 68112 KB Output is correct
6 Correct 974 ms 68120 KB Output is correct
7 Correct 922 ms 62500 KB Output is correct
8 Correct 936 ms 62500 KB Output is correct
9 Correct 987 ms 74684 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 54108 KB Output is correct
2 Correct 1044 ms 76564 KB Output is correct
3 Correct 1033 ms 74528 KB Output is correct
4 Correct 1056 ms 74684 KB Output is correct
5 Correct 1010 ms 84752 KB Output is correct
6 Correct 1014 ms 77004 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1476 ms 75204 KB Output is correct
2 Correct 1398 ms 74836 KB Output is correct
3 Correct 1526 ms 74216 KB Output is correct
4 Correct 1487 ms 74460 KB Output is correct
5 Correct 1236 ms 70868 KB Output is correct
6 Correct 1208 ms 70884 KB Output is correct
7 Correct 1018 ms 69712 KB Output is correct
8 Correct 1044 ms 69356 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 54096 KB Output is correct
2 Correct 23 ms 54108 KB Output is correct
3 Correct 26 ms 54124 KB Output is correct
4 Correct 25 ms 54104 KB Output is correct
5 Correct 27 ms 54108 KB Output is correct
6 Correct 22 ms 54108 KB Output is correct
7 Correct 23 ms 54108 KB Output is correct
8 Correct 25 ms 54108 KB Output is correct
9 Correct 24 ms 54096 KB Output is correct
10 Correct 23 ms 54104 KB Output is correct
11 Correct 23 ms 54148 KB Output is correct
12 Correct 24 ms 54108 KB Output is correct
13 Correct 28 ms 54356 KB Output is correct
14 Correct 29 ms 54316 KB Output is correct
15 Correct 28 ms 54364 KB Output is correct
16 Correct 27 ms 54364 KB Output is correct
17 Correct 29 ms 54372 KB Output is correct
18 Correct 31 ms 54240 KB Output is correct
19 Correct 27 ms 54364 KB Output is correct
20 Correct 26 ms 54364 KB Output is correct
21 Correct 27 ms 54360 KB Output is correct
22 Correct 28 ms 54352 KB Output is correct
23 Correct 238 ms 56656 KB Output is correct
24 Correct 236 ms 56688 KB Output is correct
25 Correct 231 ms 56684 KB Output is correct
26 Correct 212 ms 55768 KB Output is correct
27 Correct 211 ms 55760 KB Output is correct
28 Correct 211 ms 55636 KB Output is correct
29 Correct 171 ms 56516 KB Output is correct
30 Correct 184 ms 56372 KB Output is correct
31 Correct 156 ms 59972 KB Output is correct
32 Correct 149 ms 57428 KB Output is correct
33 Correct 223 ms 56852 KB Output is correct
34 Correct 223 ms 56960 KB Output is correct
35 Correct 218 ms 56916 KB Output is correct
36 Correct 212 ms 56908 KB Output is correct
37 Correct 223 ms 56848 KB Output is correct
38 Correct 234 ms 56984 KB Output is correct

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 54096 KB Output is correct
2 Correct 23 ms 54108 KB Output is correct
3 Correct 26 ms 54124 KB Output is correct
4 Correct 25 ms 54104 KB Output is correct
5 Correct 27 ms 54108 KB Output is correct
6 Correct 22 ms 54108 KB Output is correct
7 Correct 23 ms 54108 KB Output is correct
8 Correct 25 ms 54108 KB Output is correct
9 Correct 24 ms 54096 KB Output is correct
10 Correct 23 ms 54104 KB Output is correct
11 Correct 23 ms 54148 KB Output is correct
12 Correct 24 ms 54108 KB Output is correct
13 Correct 28 ms 54356 KB Output is correct
14 Correct 29 ms 54316 KB Output is correct
15 Correct 28 ms 54364 KB Output is correct
16 Correct 27 ms 54364 KB Output is correct
17 Correct 29 ms 54372 KB Output is correct
18 Correct 31 ms 54240 KB Output is correct
19 Correct 27 ms 54364 KB Output is correct
20 Correct 26 ms 54364 KB Output is correct
21 Correct 27 ms 54360 KB Output is correct
22 Correct 28 ms 54352 KB Output is correct
23 Correct 980 ms 69116 KB Output is correct
24 Correct 1032 ms 68980 KB Output is correct
25 Correct 1026 ms 68792 KB Output is correct
26 Correct 1033 ms 68112 KB Output is correct
27 Correct 974 ms 68120 KB Output is correct
28 Correct 922 ms 62500 KB Output is correct
29 Correct 936 ms 62500 KB Output is correct
30 Correct 987 ms 74684 KB Output is correct
31 Correct 1044 ms 76564 KB Output is correct
32 Correct 1033 ms 74528 KB Output is correct
33 Correct 1056 ms 74684 KB Output is correct
34 Correct 1010 ms 84752 KB Output is correct
35 Correct 1014 ms 77004 KB Output is correct
36 Correct 1476 ms 75204 KB Output is correct
37 Correct 1398 ms 74836 KB Output is correct
38 Correct 1526 ms 74216 KB Output is correct
39 Correct 1487 ms 74460 KB Output is correct
40 Correct 1236 ms 70868 KB Output is correct
41 Correct 1208 ms 70884 KB Output is correct
42 Correct 1018 ms 69712 KB Output is correct
43 Correct 1044 ms 69356 KB Output is correct
44 Correct 238 ms 56656 KB Output is correct
45 Correct 236 ms 56688 KB Output is correct
46 Correct 231 ms 56684 KB Output is correct
47 Correct 212 ms 55768 KB Output is correct
48 Correct 211 ms 55760 KB Output is correct
49 Correct 211 ms 55636 KB Output is correct
50 Correct 171 ms 56516 KB Output is correct
51 Correct 184 ms 56372 KB Output is correct
52 Correct 156 ms 59972 KB Output is correct
53 Correct 149 ms 57428 KB Output is correct
54 Correct 223 ms 56852 KB Output is correct
55 Correct 223 ms 56960 KB Output is correct
56 Correct 218 ms 56916 KB Output is correct
57 Correct 212 ms 56908 KB Output is correct
58 Correct 223 ms 56848 KB Output is correct
59 Correct 234 ms 56984 KB Output is correct
60 Execution timed out 2031 ms 69048 KB Time limit exceeded
61 Halted 0 ms 0 KB -