Submission #785411

#	Time	Username	Problem	Language	Result	Execution time	Memory
785411		andecaandeci	Global Warming (CEOI18_glo)	C++17	5 / 100	16 ms	4992 KiB

glo

#include<bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long, long long>
// jangan kebiasa kalah
// kalo OI, sampah aja dulu, tapi jangan menutup kemungkinan buat AC

long long n,x,arr[200069],ans,dp[200069],bef[200069];

long long lis()
{
    long long i,j;
    vector<long long> tmp(n+5,1e18);
    tmp[0] = -1e18;
    for(i=1;i<=n;i++)
    {
        j = upper_bound(tmp.begin(),tmp.end(),arr[i])-tmp.begin();
        if(tmp[j-1] < arr[i] and arr[i] < tmp[j])
        {
            tmp[j] = arr[i];
        }
    }
    j = 0;
    for(i=1;i<=n;i++)
    {
        if(tmp[i] < 1e18)
        {
            j = i;
        }
    }
    return j;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    long long i,j,s;
    cin>>n>>x;
    for(i=1;i<=n;i++)
    {
        cin>>arr[i];
        bef[i] = i;
        dp[i] = 1;
    }
    // for(i=2;i<=n;i++)
    // {
    //     for(j=1;j<i;j++)
    //     {
    //         if(arr[j] < arr[i] and dp[j] + 1 > dp[i])
    //         {
    //             dp[i] = dp[j] + 1;
    //             bef[i] = j;
    //         }
    //     }
    //     if(dp[i] > ans)
    //     {
    //         ans = dp[i];
    //         idx = i;
    //     }
    // }
    // cout<<"debug : "<<ans<<'\n';
    // for(ans=ans;ans;ans--)
    // {
    //     cout<<idx<<" ";
    //     idx = bef[idx];
    // }
    // if(x == 0ll)
    // {
    //     ans = lis();
    //     cout<<ans<<'\n';
    //     return 0;
    // }
    // if(n <= 50 and x <= 50)
    // {
    //     long long l,r;
    //     ans = 1;
    //     s = -x;
    //     // for(s=-x;s<=0;s++)
    //     // {
    //         for(l=1;l<=n;l++)
    //         {
    //             for(r=l;r<=n;r++)
    //             {
    //                 long long tmp[n+1];
    //                 tmp[0] = 0;
    //                 long long mx = 1, idx = 1;
    //                 for(i=1;i<=n;i++)
    //                 {
    //                     tmp[i] = arr[i];
    //                     if(l <= i and i <= r)
    //                     {
    //                         tmp[i] += s;
    //                     }
    //                     bef[i] = i;
    //                     dp[i] = 1;
    //                 }
    //                 for(i=2;i<=n;i++)
    //                 {
    //                     for(j=1;j<i;j++)
    //                     {
    //                         if(tmp[i] > tmp[j] and dp[i] < dp[j]+1)
    //                         {
    //                             dp[i] = dp[j]+1;
    //                             bef[i] = j;
    //                         }
    //                     }
    //                     if(dp[i] > mx)
    //                     {
    //                         mx = dp[i];
    //                         idx = i;
    //                     }
    //                 }
    //                 if(mx > ans)
    //                 {
    //                     ans = mx;
    //                     // cout<<"left : "<<l<<", right : "<<r<<'\n';
    //                     // cout<<"cur_max : "<<ans<<" ; bt : ";
    //                     while(mx--)
    //                     {
    //                         cout<<idx<<" ";
    //                         idx = bef[idx];
    //                     }
    //                     cout<<'\n';
    //                 }
    //             }
    //         }
    //     // }
    //     cout<<ans<<'\n';
    //     return 0;
    // }
    if(n <= 1000)
    {
        long long idx = 1,mx;
        for(i=2;i<=n;i++)
        {
            for(j=1;j<i;j++)
            {
                if(arr[i] > arr[j] and dp[i] < dp[j] + 1)
                {
                    dp[i] = dp[j] + 1;
                    bef[i] = j;
                }
            }
        }
        for(i=1;i<=n;i++)
        {
            if(dp[i] > ans)
            {
                ans = dp[i];
                idx = i;
            }
        }
        vector<long long> vec;
        mx = ans;
        while(mx--)
        {
            vec.push_back(idx);
            idx = bef[idx];
        }
        reverse(vec.begin(),vec.end());
        vector<pll> pos;
        pll posisi = {vec[0],vec[0]};
        for(i=1;i<vec.size();i++)
        {
            if(vec[i]-vec[i-1] == 1)
            {
                posisi.se = vec[i];
            }
            else
            {
                pos.push_back(posisi);
                posisi = {vec[i],vec[i]};
            }
        }
        pos.push_back(posisi);
        mx = 0, idx = 0;
        for(i=0;i<pos.size();i++)
        {
            j = pos[i].se-pos[i].fi+1;
            if(j > mx)
            {
                mx = j;
                idx = i;
            }
        }
        for(i=pos[idx].fi;i<=pos[idx].se;i++)
        {
            arr[i] += -x;
        }
        ans = max(ans,lis());
        cout<<ans<<'\n';
        return 0;
    }
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:167:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |         for(i=1;i<vec.size();i++)
      |                 ~^~~~~~~~~~~
glo.cpp:181:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |         for(i=0;i<pos.size();i++)
      |                 ~^~~~~~~~~~~
glo.cpp:41:19: warning: unused variable 's' [-Wunused-variable]
   41 |     long long i,j,s;
      |                   ^

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