Submission #959074

#	Time	Username	Problem	Language	Result	Execution time	Memory
959074		Younis_Dwai	Global Warming (CEOI18_glo)	C++14	10 / 100	174 ms	18472 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];
            v.pb(b[i]);
    }
    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 i=1;i<=n;i++) b[i]=mp[b[i]];
    for(int i=1;i<=n;i++){
        dp[i]=1+query(1,0,n,0,b[i]-1);
        res=max(res,dp[i]);
        upd(1,0,n,b[i],dp[i]);
    }
    cout<<res;
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25