Submission #1096705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096705		talabuado	Global Warming (CEOI18_glo)	C++14	10 / 100	223 ms	22356 KiB

glo

#include <bits/stdc++.h>
using namespace std;
#define intt long long
#define fi first
#define se second
const int N = 5e5+3;
intt a[N],n,m,x;
pair<intt,intt> b[N];
map<intt,intt> mp;
intt d[N],st[4*N];
intt dp[N];
intt ans=0;
void update(int id ,int l ,int r ,int pos ,intt val){
    if(pos < l || pos > r){
        return;
    }if(l==r){
        st[id]=val;
        return;
    }
    int m=(l+r)/2;
    update(id*2,l , m , pos ,val);
    update(id*2+1,m+1,r , pos,val);
    st[id] =max(st[id*2+1],st[id*2]);
}
intt get(int id ,int l ,int r ,int u ,int v){
    if(u >r || v < l ){
        return -1e9;
    }else if(u<= l &&r <=v){
        return st[id];
    }
    intt m =(l+r)/2;
    return max(get(id*2,l,m,u,v),get(id*2+1,m+1,r ,u ,v));
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("DAYDEP.INP","r",stdin);
//    freopen("DAYDEP.OUT","w",stdout);
     cin>>n>>x;
     for(int i=1 ; i<=n;i++){
            cin>>a[i];
            mp[a[i]]=1;
     }
     intt m=0;
     for(pair<intt,intt> v :mp){
         mp[v.fi]=++m;
     }
     for(int i=1 ; i<=n;i++){
        a[i]=mp[a[i]];
     }
     for(int i=1 ; i<=n;i++){
        dp[a[i]]=1;
//        update(1,1,n,a[i],1);

//        update(1,1,n,a[i],max((intt)1,get(1,1,n,1,a[i]-1)+1));
        update(1,1,n,a[i],max((intt)1,1+get(1,1,n,1,a[i]-1)));
//        for(int j=1 ; j<=a[i]-1;j++){
//            dp[a[i]]= max(dp[a[i]],dp[j]+1);
//        }
     }
     for(int i=1 ; i<=n;i++){
//        cout<<get(1,1,n,a[i],a[i])<<endl;
     }
     cout<<get(1,1,n,1,n);
}

• 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