Submission #959091

#	Time	Username	Problem	Language	Result	Execution time	Memory
959091		Younis_Dwai	Global Warming (CEOI18_glo)	C++14	15 / 100	2058 ms	262144 KiB

glo

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25