oj.uz

Submission #948240

# Submission time Handle Problem Language Result Execution time Memory
948240 2024-03-18T01:14:34 Z ezzzay Global Warming (CEOI18_glo) C++14
25 / 100
 2000 ms 23892 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
#define double long double
const int N=2e5+5;
int a[N];
int dp[N];
int b[N];
int n;

int st[4*N];
void update(int node, int L, int R, int idx, int val){
    if(L==R){
        st[node]=val;
        return ;
    }
    int mid=(L+R)/2;
    if(L<=idx and idx<=mid){
        update(node*2,L,mid,idx,val);
    }
    else {
        update(node*2+1,mid+1,R,idx,val);
    }
    st[node]=max(st[node*2],st[node*2+1]);
}
int find(int node, int L , int R, int l, int r){
    if(l>R or L>r)return 0;
    if(l<=L and R<=r)return st[node];
    int mid=(L+R)/2;
    return max( find(node*2,L,mid,l,r) , find(node*2+1,mid+1,R,l,r)) ;
}
void sbtsk4(){
    map<int,int>mp;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mp[a[i]];
    }
    int ans=0;
    int idx=1;
    for(auto it=mp.begin();it!=mp.end();it++){
        it->ss = idx++;
    }
    for(int i=1;i<=n;i++)a[i]=mp[a[i]];
    for(int i=1;i<=n;i++){
        dp[i]= find(1,1,n,1,a[i]-1)+1;
        dp[i]=max(dp[i],1LL);
        ans=max(dp[i],ans);
        update(1,1,n,a[i],dp[i]);
    }
    cout<<ans;
}
int fun(int l, int r, int x){
    for(int i=0;i<=4000;i++)st[i]=0;
    for(int i=0;i<=1000;i++){
        dp[i]=0;
    }
    
    for(int i=1;i<=n;i++){
        if(l<=i and i<=r)b[i]=a[i]-x;
        else b[i]=a[i];
    }
    map<int,int>mp;
    for(int i=1;i<=n;i++){
        
        mp[b[i]];
    }
    int ans=0;
    int idx=1;
    for(auto it=mp.begin();it!=mp.end();it++){
        it->ss = idx++;
    }
    for(int i=1;i<=n;i++)b[i]=mp[b[i]];
    for(int i=1;i<=n;i++){
        dp[i]= find(1,1,n,1,b[i]-1)+1;
        dp[i]=max(dp[i],1LL);
        ans=max(dp[i],ans);
        update(1,1,n,b[i],dp[i]);
    }
    return st[1];
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int x;
    cin>>n>>x;
    if(x==0){
        sbtsk4();
        return 0;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int ans=0;
    for(int l=1;l<=1;l++){
        for(int r=l+1;r<=n;r++){
            for(int p= -x;p<=x;p++){
                ans=max(ans,fun(l,r,p));
            }
        }
    }
    cout<<ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 9 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 33 ms 6492 KB Output is correct
15 Correct 11 ms 6492 KB Output is correct
16 Correct 11 ms 6644 KB Output is correct
17 Correct 1 ms 6488 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 9 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 33 ms 6492 KB Output is correct
15 Correct 11 ms 6492 KB Output is correct
16 Correct 11 ms 6644 KB Output is correct
17 Correct 1 ms 6488 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Execution timed out 2078 ms 6488 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 23632 KB Output is correct
2 Correct 216 ms 23892 KB Output is correct
3 Correct 230 ms 23572 KB Output is correct
4 Correct 209 ms 23604 KB Output is correct
5 Correct 82 ms 16656 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 10556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2065 ms 14676 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6488 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 9 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 33 ms 6492 KB Output is correct
15 Correct 11 ms 6492 KB Output is correct
16 Correct 11 ms 6644 KB Output is correct
17 Correct 1 ms 6488 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Execution timed out 2078 ms 6488 KB Time limit exceeded
20 Halted 0 ms 0 KB -