oj.uz

Submission #948241

# Submission time Handle Problem Language Result Execution time Memory
948241 2024-03-18T01:17:41 Z ezzzay Global Warming (CEOI18_glo) C++14
25 / 100
 2000 ms 23844 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<=2000;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;
    int l=1;
    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 6492 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 6744 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 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 6744 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 8 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 32 ms 6492 KB Output is correct
15 Correct 11 ms 6492 KB Output is correct
16 Correct 10 ms 6488 KB Output is correct
17 Correct 1 ms 6492 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 6492 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 6744 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 8 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 32 ms 6492 KB Output is correct
15 Correct 11 ms 6492 KB Output is correct
16 Correct 10 ms 6488 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Execution timed out 2033 ms 6492 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 23748 KB Output is correct
2 Correct 205 ms 23844 KB Output is correct
3 Correct 204 ms 23636 KB Output is correct
4 Correct 202 ms 23636 KB Output is correct
5 Correct 83 ms 16468 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2001 ms 10692 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 2054 ms 14688 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 6492 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 6744 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 8 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 32 ms 6492 KB Output is correct
15 Correct 11 ms 6492 KB Output is correct
16 Correct 10 ms 6488 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Execution timed out 2033 ms 6492 KB Time limit exceeded
20 Halted 0 ms 0 KB -