oj.uz

Submission #959074

# Submission time Handle Problem Language Result Execution time Memory
959074 2024-04-07T13:05:58 Z Younis_Dwai Global Warming (CEOI18_glo) C++14
10 / 100
 174 ms 18472 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];
            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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 18064 KB Output is correct
2 Correct 174 ms 18472 KB Output is correct
3 Correct 168 ms 16668 KB Output is correct
4 Correct 167 ms 16600 KB Output is correct
5 Correct 89 ms 10956 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5940 KB Output is correct
2 Correct 33 ms 5856 KB Output is correct
3 Correct 35 ms 5856 KB Output is correct
4 Incorrect 18 ms 4316 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 9168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -