Submission #1127477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127477		O_Elmasry	Global Warming (CEOI18_glo)	C++20	10 / 100	1008 ms	89040 KiB

glo

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...)
#endif
#define endl '\n'
#define int int64_t
const long long mod = 1000000007, MaxN = 200005, INF = 1e18;
struct Cordinate_Compression
{
  set<int> vals;
  map<int, int> val_to_cord, cord_to_val;
  void init(set<int> s)
  {
    vals = s;
    int idx = 1;
    for (auto i : vals)
    {
      cord_to_val[idx] = i;
      val_to_cord[i] = idx++;
    }
  }
  int incr(int x)
  {
    return val_to_cord[x];
  }
  int decr(int idx)
  {
    return cord_to_val[idx];
  }
  int lower_bound(int x){
    return *--vals.upper_bound(x);
  }
};
template<typename T>
struct Segment_Tree{
  int sz = 1, N;
  T Neutral;
  vector<T>tree;
  function<T(T, T)> merge;
  Segment_Tree(int _N, function< T (T, T) >_merge, T _Neutral = 0){
    merge = _merge;
    while(sz < _N)sz *= 2;
    N = sz * 2;
    tree.resize(N);
    Neutral = _Neutral;
  }
  #define left node * 2 + 1
  #define right node * 2 + 2
  void build(int idx, T val, int node, int l, int r){
    if(l == r)return void(tree[node] = val);
    int mid = l + r >> 1;
    if(idx <= mid)build(idx, val, left, l, mid);
    else build(idx, val, right, mid + 1, r);
    tree[node] = merge(tree[left], tree[right]);
  }
  void build(int idx, int val){
    build(idx, val, 0, 0, sz - 1);
  }

  T get(int lq, int rq, int node, int l, int r){
    if(l > rq || r < lq)return Neutral;
    if(l >= lq && r <= rq)return tree[node];
    int mid = l + r >> 1;
    return merge(get(lq, rq, left, l, mid), get(lq, rq, right, mid + 1, r));
  }
  T get(int lq, int rq){
    return get(lq, rq, 0, 0, sz - 1);
  }
  #undef left
  #undef right
};
void solve()
{
  int N, x;
  cin >> N >> x;
  vector<int> a(N + 1), lis, lds, best(N + 1);
  map<int, multiset<int>> st;
  Cordinate_Compression cc;
  Segment_Tree<int>seg(N + 3, [](int a, int b){
    return max(a, b);
  }, 0);
  for (int i = 1; i <= N; i++)
  {
    cin >> a[i];
    if (i == 1)
    {
      lis.push_back(a[i]);
      best[i] = 1;
      st[a[i]].insert(best[i]);
      continue;
    }
    int pos = lower_bound(lis.begin(), lis.end(), a[i]) - lis.begin();
    if (pos == lis.size())
    {
      lis.push_back(a[i]);
    }
    else
    {
      lis[pos] = a[i];
    }
    best[i] = pos + 1;
    st[a[i]].insert(best[i]);
  }
  set<int>s(a.begin(), a.end());
  cc.init(s);
  for(auto [x, y] : st){
    seg.build(cc.incr(x), *--y.end());
  }
  int ans = seg.get(0, N + 1);
  dbg(ans);
  for(int i = N;i >= 1;i--){
    st[a[i]].erase(st[a[i]].find(best[i]));
    int y = (st[a[i]].empty() ? 0 : *--st[a[i]].end());
    seg.build(cc.incr(a[i]), y);
    int pos = a[i] + x - 1;
    int lb = cc.lower_bound(pos);
    dbg(i, a[i], x, best[i], st[a[i]], pos, lb);
    int cur = seg.get(0, cc.incr(lb));
    if(lds.empty()){
      lds.push_back(a[i]);
      ans = max(ans, cur + 1);
      continue;
    }
    int L = -1, R = lds.size();
    while(L + 1 < R){
      int mid = L + R >> 1;
      if(lds[mid] > a[i]){
        L = mid;
      }
      else{
        R = mid;
      }
    }
    dbg(cur, L, a[i]);
    ans = max(ans, cur + L + 2);
  }
  cout << ans << endl;
}
signed main()
{
  ios::sync_with_stdio(0);
  cin.tie(nullptr);
  cout.tie(nullptr);
#ifdef LOCAL
  FileRedirect("test");
#endif
  // freopen("file.in","r",stdin);
  // freopen("file.out","w",stdout);
  int tc = 1;
  // cin >> tc;
  while (tc--)
    solve();
}

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