Submission #70885

#	Time	Username	Problem	Language	Result	Execution time	Memory
70885		georgerapeanu	Global Warming (CEOI18_glo)	C++11	100 / 100	390 ms	19096 KiB

glo

#include <iostream>
#include <vector>

using namespace std;

const int NMAX = 2e5;

int n,x;
int V[NMAX + 5];

vector<int> L_PREF[NMAX + 5];
int len_pref;
vector<int> L_SUFF[NMAX + 5];
int len_suff;
int ans = 0;
int dp_pref[NMAX + 5];

int main() {
    cin >> n >> x;

    for(int i = 1;i <= n;i++){
       cin >> V[i];
    }

   V[0] = -(1 << 30);
   V[n + 1] = 1 << 30;

    L_PREF[0].push_back(0);
    len_pref = 0;

    for(int i = 1;i <= n;i++){
       int st = 0,dr = len_pref + 1;
       while(dr - st > 1){
          int mid = (st + dr) / 2;
          if(V[L_PREF[mid].back()] < V[i]){
             st = mid;
          }
          else{
             dr = mid;
          }
       }

       dp_pref[i] = st + 1;

       if(st == len_pref){
          len_pref++;
          L_PREF[len_pref].push_back(i);
       }
       else{
          L_PREF[st + 1].push_back(i);
       }
    }

    ans = len_pref;

    L_SUFF[0].push_back(n + 1);
    len_suff = 0;

   for(int i = n;i;i--){
       int st = 0,dr = len_suff + 1;
       while(dr - st > 1){
          int mid = (st + dr) / 2;
          if(V[L_SUFF[mid].back()] > V[i]){
             st = mid;
          }
          else{
             dr = mid;
          }
       }
       if(st == len_suff){
          len_suff++;
          L_SUFF[len_suff].push_back(i);
       }
       else{
          L_SUFF[st + 1].push_back(i);
       }

       L_PREF[dp_pref[i]].pop_back();
       while(L_PREF[len_pref].empty()){
          len_pref--;
       }

       int st2 = 0,dr2 = len_pref + 1;
       while(dr2 - st2 > 1){
          int mid = (st2 + dr2) / 2;
          if(V[L_PREF[mid].back()] < V[i] + x){
             st2 = mid;
          }
          else{
             dr2 = mid;
          }
       }
       ans = max(ans,st2 + st + 1);
    }

    cout << ans;

    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