제출 #897837

#제출 시각아이디문제언어결과실행 시간메모리
897837alexddGlobal Warming (CEOI18_glo)C++17
100 / 100
665 ms43976 KiB
#include<bits/stdc++.h>
using namespace std;
int n,d;
int a[200005];
map<int,int> mp;
map<int,int> nrm;
int cate;

int aib[400005][2];
int qry(int poz, int care)
{
    int aux=0;
    for(int i=poz;i>0;i-=i&(-i))
        aux = max(aux, aib[i][care]);
    return aux;
}
void upd(int poz, int newv, int care)
{
    for(int i=poz;i<=cate;i+=i&(-i))
        aib[i][care] = max(aib[i][care], newv);
}

int solve_minus()
{
    for(int i=1;i<=n;i++)
    {
        upd(nrm[a[i]],qry(nrm[a[i]]-1,0)+1,0);
        upd(nrm[a[i]],qry(nrm[a[i]]-1,1)+1,1);
        upd(nrm[a[i]-d],qry(nrm[a[i]],0),1);
    }
    return max(qry(cate,0),qry(cate,1));
}
signed main()
{
    cin>>n>>d;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        mp[a[i]]++;
        mp[a[i]-d]++;
    }
    for(auto it:mp)
        nrm[it.first]=++cate;
    cout<<solve_minus();
    return 0;
}
/**

8 10
7 3 5 12 2 7 3 4

dp[i][0] = cea mai lunga secventa care se termina cu valoarea i si pe care inca nu s-a folosit operatia
dp[i][1] = cea mai lunga secventa care se termina cu valoarea i si pe care s-a folosit deja operatia

dp[a[i] - d][1] max= dp[orice < a[i]][0] + 1

*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...