Submission #907238

#TimeUsernameProblemLanguageResultExecution timeMemory
907238heeheeheehaawGlobal Warming (CEOI18_glo)C++17
100 / 100
725 ms41888 KiB
#include <bits/stdc++.h>

using namespace std;

map<int, int> mp1, mp2;
int cnt = 0;
int v[200005];
int aib1[400005], aib2[400005];

void upd1(int poz, int val)
{
    for(int i = poz; i <= cnt; i += (i & (-i)))
        aib1[i] = max(aib1[i], val);
    return;
}

int qry1(int poz)
{
    int maxx = 0;
    for(int i = poz; i >= 1; i -= (i & (-i)))
        maxx = max(maxx, aib1[i]);
    return maxx;
}

void upd2(int poz, int val)
{
    for(int i = poz; i <= cnt; i += (i & (-i)))
        aib2[i] = max(aib2[i], val);
    return;
}

int qry2(int poz)
{
    int maxx = 0;
    for(int i = poz; i >= 1; i -= (i & (-i)))
        maxx = max(maxx, aib2[i]);
    return maxx;
}

signed main()
{
    int n, k;
    cin>>n>>k;
    for(int i = 1; i <= n; i++)
        cin>>v[i], mp1[v[i]] = 1, mp1[v[i] - k] = 1;
    for(auto it : mp1)
        mp2[it.first] = ++cnt;
    for(int i = 1; i <= n; i++)
    {
        upd2(mp2[v[i]], qry2(mp2[v[i]] - 1) + 1);
        upd2(mp2[v[i]], qry1(mp2[v[i]] - 1) + 1);
        upd1(mp2[v[i] - k], qry1(mp2[v[i] - k] - 1) + 1);
    }

    cout<<qry2(cnt);
    return 0;
}
#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...