Submission #1245604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245604		Jovica	Global Warming (CEOI18_glo)	C++20	100 / 100	633 ms	43492 KiB

glo

#include <bits/stdc++.h>

using namespace std;
int const maxn = 2e5+1;
int dp[maxn],lis[maxn];

void LIS(int n,vector<int> &v)
{
    vector<int> s;
    for (int i=n-1;i>=0;i--)
    {
        int x = -v[i];
        int p = lower_bound(s.begin(),s.end(),x) - s.begin();
        if (p == s.size()) s.push_back(x);
        else s[p] = x;

        dp[i] = p+1;
    }
    s = {};
    for (int i=0;i<n;i++)
    {
        int p = lower_bound(s.begin(),s.end(),v[i]) - s.begin();
        if (p == s.size()) s.push_back(v[i]);
        else s[p] = v[i];
        lis[i] = p;
    }

    //for (int i=0;i<n;i++) cout<<dp[i]<< " ";
}

map<int,int> prevod;
void kompres(int n,vector<int> &v,int k)
{
    set<int> s;
    for (int i=0;i<n;i++){
        s.insert(v[i]);
        s.insert(v[i]+k-1);
    }
    int p = 1;

    for (auto a: s)
    {
        prevod[a] = p;
        p++;
    }
}

int drvo[2000000];

int najdi(int l,int r,int poz,int const levo,const int desno)
{
    if (r<levo || desno<l) return 0;
    if (levo<=l && r<=desno) return drvo[poz];

    int mid = (l+r)/2;
    return max(najdi(l,mid,poz*2,levo,desno),najdi(mid+1,r,poz*2+1,levo,desno));
}

int update(int l,int r,int poz,const int p,int const k)
{
    if (p<l || r<p) return drvo[poz];
    if (l == r)
    {
        drvo[poz] = max(drvo[poz],k);
        return drvo[poz];
    }
    int mid = (l+r)/2;
    drvo[poz] = max(update(l,mid,poz*2,p,k),update(mid+1,r,poz*2+1,p,k));
    return drvo[poz];
}

int main()
{
    int n,k;
    cin>>n>>k;vector<int> v(n);
    for (int i=0;i<n;i++) cin>>v[i];

    LIS(n,v);

    kompres(n,v,k);

    int odg = 0;
    int ns = 1;while (ns<n*2) ns*=2;
    for (int i=0;i<n;i++){
        odg = max(odg,dp[i] + najdi(1,ns,1,1,prevod[v[i]+k-1]));
        //cout<<"odg "<<i<<": "<<dp[i] <<" + "<<najdi(1,ns,1,1,prevod[v[i]+k-1])<<endl;
        //cout<<"dodava "<<lis[i]<<endl;

        update(1,ns,1,prevod[v[i]],lis[i]+1);
    }

    cout<<odg<<endl;
    return 0;
}
/*
8 100
7 3 5 12 2 7 3 4

10 10
1 2 5 6 4 2 3 8 7 10

*/

• 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