oj.uz

Submission #959091

# Submission time Handle Problem Language Result Execution time Memory
959091 2024-04-07T13:24:26 Z Younis_Dwai Global Warming (CEOI18_glo) C++14
15 / 100
 2000 ms 262144 KB 
#include <bits/stdc++.h>
//#define int  long long
#define F first
#define S second
#define pb push_back
#define in insert
#define mid (l+r)/2
#define endl "\n"
//#define pop pop_back
using namespace std ;
int n,x,tree[8000009],b[200009],res=0,dp[200009],c[200009];
int query(int node , int l , int  r , int s , int e){
    if(l>=s && r<=e) return tree[node];
    else if(l>e || r<s) return 0;
    return max(query(node*2,l,mid,s,e),query(node*2+1,mid+1,r,s,e));
}
void upd(int node , int  l , int r , int id , int v){
     if(l==r){
        tree[node]=v;
        return ;
     }
     else if(id<=mid) upd(node*2,l,mid,id,v);
     else upd(node*2+1,mid+1,r,id,v);
     tree[node]=max(tree[node*2],tree[node*2+1]);
     return ;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin>>n>>x;
    vector<int> v;
    for(int i=1;i<=n;i++){
            cin>>b[i];
            for(int j=-x;j<=x;j++) v.pb(b[i]+j);
    }
    sort(begin(v),end(v));v.resize(unique(v.begin(),v.end())-v.begin());
    map<int,int> mp;int t=0;for(auto u : v) mp[u]=++t;
    for(int j=-x;j<=x;j++){
        for(int l=1;l<=n;l++){
            for(int r=l;r<=n;r++){
                for(int k=1;k<=n;k++) c[k]=mp[b[k]];
                for(int k=l;k<=r;k++) c[k]=mp[b[k]+j];
                for(int i=0;i<=4*t;i++){
                    tree[i]=0;
                    dp[i]=0;
                }
                for(int i=1;i<=n;i++){
                    int xx=1+query(1,0,t,0,c[i]-1);
                    res=max(res,xx);
                    upd(1,0,t,c[i],xx);
                }
            }
        }
    }
    cout<<res;
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 92 ms 4444 KB Output is correct
13 Correct 3 ms 4444 KB Output is correct
14 Correct 451 ms 4600 KB Output is correct
15 Correct 165 ms 4700 KB Output is correct
16 Correct 159 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 4444 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 92 ms 4444 KB Output is correct
13 Correct 3 ms 4444 KB Output is correct
14 Correct 451 ms 4600 KB Output is correct
15 Correct 165 ms 4700 KB Output is correct
16 Correct 159 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 4444 KB Output is correct
19 Runtime error 215 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 20.0

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

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 108 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 92 ms 4444 KB Output is correct
13 Correct 3 ms 4444 KB Output is correct
14 Correct 451 ms 4600 KB Output is correct
15 Correct 165 ms 4700 KB Output is correct
16 Correct 159 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 4444 KB Output is correct
19 Runtime error 215 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -