Submission #907237

#	Time	Username	Problem	Language	Result	Execution time	Memory
907237		heeheeheehaaw	Global Warming (CEOI18_glo)	C++17	100 / 100	809 ms	43608 KiB

glo

#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<<max(qry1(cnt), qry2(cnt));
    return 0;
}

• 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