oj.uz

Submission #959094

# Submission time Handle Problem Language Result Execution time Memory
959094 2024-04-07T13:26:24 Z Younis_Dwai Global Warming (CEOI18_glo) C++14
25 / 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++){
        if(j==0){
             for(int k=1;k<=n;k++) c[k]=mp[b[k]];
                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);
                }
                continue ;
        }
        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 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 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 4444 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 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 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 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 111 ms 4564 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 537 ms 4600 KB Output is correct
15 Correct 203 ms 4588 KB Output is correct
16 Correct 196 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 4440 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 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 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 111 ms 4564 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 537 ms 4600 KB Output is correct
15 Correct 203 ms 4588 KB Output is correct
16 Correct 196 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 4440 KB Output is correct
19 Runtime error 219 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 16880 KB Output is correct
2 Correct 173 ms 16964 KB Output is correct
3 Correct 169 ms 16840 KB Output is correct
4 Correct 168 ms 16848 KB Output is correct
5 Correct 79 ms 10200 KB Output is correct

Subtask #5
0 / 20.0

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

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 119 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 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 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 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 111 ms 4564 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 537 ms 4600 KB Output is correct
15 Correct 203 ms 4588 KB Output is correct
16 Correct 196 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 4440 KB Output is correct
19 Runtime error 219 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -