Submission #779572

#	Time	Username	Problem	Language	Result	Execution time	Memory
779572		Trisanu_Das	Global Warming (CEOI18_glo)	C++17	0 / 100	2081 ms	3280 KiB

glo

#include <bits/stdc++.h>
using namespace std;
 
int n, x, a[200005], BIT[2][200005], sort_a[200005];
 
void upd(int k, int idx, int val){
  for(int i = idx; i <= n; i += (i & (-i))) BIT[k][i] = max(BIT[k][i], val);
}
 
int qry(int k, int idx){
  int ans = 0;
  for(int i = idx; i; i -= (i & (-i))) ans = max(ans, BIT[k][i]);
  return ans;
}
 
int main(){
  cin >> n >> x;
  for(int i = 0; i < n; i++){
    cin >> a[i]; 
    sort_a[i] = a[i];
  }
  sort(sort_a, sort_a + n);
  for(int i = 0; i < n; i++){
    int last = lower_bound(sort_a, sort_a + n, a[i]) - sort_a;
    int a_ = qry(0, last), b = qry(0, lower_bound(sort_a, sort_a + n, a[i] + x) - sort_a), c = qry(1, last);
    upd(0, last, a_ + 1); upd(1, last, max(b, c) + 1);
  }
  cout << qry(1, n) << '\n';
}

• Subtask 1: 0 / 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