Submission #1183585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183585		vyaduct	Global Warming (CEOI18_glo)	C++20	100 / 100	385 ms	47216 KiB

glo

#include <algorithm>
#include <bits/stdc++.h>
#include <queue>
using namespace std;
typedef long long ll;

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(x) 42
#endif

void setIo(string in="", string out=""){
  if (!in.empty() && !out.empty()){
    freopen(in.c_str(), "r", stdin);
    freopen(out.c_str(), "w", stdout);
  }
  ios::sync_with_stdio(false);
  cin.tie(0);
}
 
#define all(c)      (c).begin(), (c).end()
#define sz(c)       (int)(c).size()
#define vt          vector
#define pb          push_back
#define F           first
#define S           second
#define P           pair

class segtree {
private:
  struct node {
    ll x;
  };
  node single(ll v){
    return {v};
  }
  node merge(node a, node b){
    return single(max(a.x, b.x));
  }

  int size;
  vector<node> arr;
  node fill = single(0ll);
  node neutral = single(0ll);

  void set(int i, ll v, int x, int lx, int rx){
    if (rx - lx == 1){
      arr[x] = single(v);
      return;
    }
    int m = (lx+rx)/2;
    if (i < m){
      set(i, v, 2*x+1, lx, m);
    } else {
      set(i, v, 2*x+2, m, rx);
    }
    arr[x] = merge(arr[2*x+1], arr[2*x+2]);
  }
  node query(int l, int r, int x, int lx, int rx){
    if (l >= rx || r <= lx) return neutral;
    if (l <= lx && rx <= r) return arr[x];
    int m = (lx+rx)/2;
    node s1 = query(l, r, 2*x+1, lx, m);
    node s2 = query(l, r, 2*x+2, m, rx);
    return merge(s1,s2);
  }
public:
  void init(int n) {size = 1;while(size < n) size *= 2;arr.assign(2*size, fill);}
  void set(int i, ll v) {return set(i, v, 0, 0, size);}
  ll query(int l, int r) {return query(l, r, 0, 0, size).x;}
  void clear(){
    for (node &x: arr) x = single(0LL);
  }
};

void solve(){
  int n; ll x;
  cin>>n>>x;
  vt<ll> t(n);
  vt<int> end(n, 1), start(n, 1);
  for (int i=0;i<n;i++) cin>>t[i];

  vt<ll> indices = t;
  sort(all(indices));
  indices.erase(unique(all(indices)), indices.end());
  auto c = [&](ll x){return lower_bound(all(indices), x) - indices.begin();};
  segtree st; st.init(sz(indices));

  for (int i=0;i<n;i++){
    int ind = c(t[i]);
    end[i] = st.query(0, ind)+1;
    st.set(ind, end[i]);
  }

  st.clear();
  for (int i=n-1;i>=0;i--){
    int ind = c(t[i]);
    start[i] = st.query(ind+1, n)+1;
    st.set(ind, start[i]);
  }

  // BAZOOKA
  for (int i=0;i<n;i++) {
    indices.pb(t[i]-x);
  }
  sort(all(indices));
  indices.erase(unique(all(indices)), indices.end());

  segtree final; final.init(sz(indices));
  multiset<ll, greater<>> order[sz(indices)];

  int best=1;
  for (int i=0;i<n;i++){
    int ind = c(t[i]);
    order[ind].insert(start[i]);
    final.set(ind, *order[ind].begin());
  }

  int ans=1;
  for (int i=0;i<n;i++){
    // Removings
    int og = c(t[i]);
    if (order[og].size()>0){
      order[og].erase(order[og].find(start[i]));
      final.set(og, *order[og].begin());
    } else {
      final.set(og, 0);
    }

    int ind = c(t[i]-x);
    int query = final.query(ind+1, sz(indices));
    ans = max(ans, query+end[i]);
  }
  cout << min(ans,n) << endl;
}

int main() {
  setIo();
  int tt=1; 
  // cin>>tt;
  while(tt--) solve(); 
  return 0;
} 

Compilation message (stderr)

glo.cpp: In function 'void setIo(std::string, std::string)':
glo.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen(in.c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen(out.c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• 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