Submission #897837

#	Time	Username	Problem	Language	Result	Execution time	Memory
897837		alexdd	Global Warming (CEOI18_glo)	C++17	100 / 100	665 ms	43976 KiB

glo

#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

*/

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