Submission #437756

#	Time	Username	Problem	Language	Result	Execution time	Memory
437756		definitelynotmee	Global Warming (CEOI18_glo)	C++98	100 / 100	162 ms	10216 KiB

glo

#include <bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MOD = 1e9 + 7;
const int MAXN = 1e6+1;



int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, x;
    cin >> n >> x;
    vector<int> v(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];

    vector<vector<pii>> lds;
    for(int i = n-1; i >0; i--){
        int ini = 0, fim = lds.size();
        while(ini!=fim){
            int m = (ini+fim)>>1;
            if(lds[m][lds[m].size()-1].ss <= v[i]){
                fim = m;
            } else ini = m+1;
        }
        if(ini==lds.size())
            lds.push_back({});
        lds[ini].push_back({i,v[i]});
    }
    vector<int>lis;
    int resp = 0;
    for(int i = 0; i < n; i++){
        int ini = 0, fim = lis.size();
        while(ini!=fim){
            int m = (ini+fim)>>1;
            if(lis[m] >= v[i]){
                fim = m;
            } else ini = m+1;
        }
        if(ini==lis.size())
            lis.push_back(v[i]);
        else lis[ini] = v[i];
        int i1 = -1, f1 = lds.size()-1;
        while(i1!=f1){
            int m = (i1+f1+1)>>1;
            int i2 = -1, f2 = lds[m].size()-1;
            while(i2!=f2){
                int mm = (i2+f2+1)>>1;
                if(lds[m][mm].ff > i)
                    i2 = mm;
                else f2 = mm-1;
            }
            int cur = i2 == -1 ? -INF : lds[m][i2].ss;
            if(cur > v[i]-x)
                i1 = m;
            else f1 = m-1;
        }
        resp = max(resp, ini+i1+2);
    }
    cout << resp << '\n';
    return 0;

}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         if(ini==lds.size())
      |            ~~~^~~~~~~~~~~~
glo.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         if(ini==lis.size())
      |            ~~~^~~~~~~~~~~~

• 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