제출 #1219513

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219513		thewizardman	Global Warming (CEOI18_glo)	C++20	100 / 100	173 ms	11440 KiB

glo

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define plpll pair<ll, pll>
#define pipii pair<int, pii>
#define plpii pair<ll, pii>
#define pipll pair<int, pll>
#define lll tuple<ll, ll, ll>
#define iii tuple<int, int, int>
#define lii tuple<ll, int, int>
#define lli tuple<ll, ll, int>
#define md 1000000007LL
#define linf 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define lninf 0xc0c0c0c0c0c0c0c0
#define ninf 0xc0c0c0c0
#define bruh ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

template<class T1, class T2>
istream& operator>>(istream& in, pair<T1, T2>& p) {
  return in >> p.first >> p.second;
}

template<class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
  return out << p.first << ' ' << p.second;
}

template<size_t I = 0, typename... Ts>
typename enable_if<I == sizeof...(Ts), istream&>::type
read_tuple(istream& in, tuple<Ts...>& t) { return in; }

template<size_t I = 0, typename... Ts>
typename enable_if<I < sizeof...(Ts), istream&>::type
read_tuple(istream& in, tuple<Ts...>& t) {
  in >> get<I>(t);
  return read_tuple<I + 1>(in, t);
}

template<typename... Ts>
istream& operator>>(istream& in, tuple<Ts...>& t) {
  return read_tuple(in, t);
}

template<size_t I = 0, typename... Ts>
typename enable_if<I == sizeof...(Ts), void>::type
write_tuple(ostream& out, const tuple<Ts...>&) {}

template<size_t I = 0, typename... Ts>
typename enable_if<I < sizeof...(Ts), void>::type
write_tuple(ostream& out, const tuple<Ts...>& t) {
  if (I) out << ' ';
  out << get<I>(t);
  write_tuple<I + 1>(out, t);
}

template<typename... Ts>
ostream& operator<<(ostream& out, const tuple<Ts...>& t) {
  write_tuple(out, t);
  return out;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& v) {
  for (auto& x : v) in >> x;
  return in;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
  for (size_t i = 0; i < v.size(); ++i)
    out << (i ? " " : "") << v[i];
  return out;
}

ll n, x, a[200000], fw[400000][2];
vector<ll> b;

ll compress(ll x) {
  return lower_bound(b.begin(), b.end(), x) - b.begin();
}

ll query(int i, bool inc) {
  ll ret = 0;
  for (; i >= 0; i = (i & (i+1)) - 1) ret = max(ret, fw[i][inc]);
  return ret;
}

void update(int i, bool inc, ll val) {
  for (; i < b.size(); i = i | (i+1)) fw[i][inc] = max(fw[i][inc], val);
}

int main() {
  bruh;
  cin >> n >> x;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) b.push_back(a[i]), b.push_back(a[i]+x);
  sort(b.begin(), b.end());
  b.erase(unique(b.begin(), b.end()), b.end());

  for (int i = 0; i < n; i++) {
    ll q1 = query(compress(a[i])-1, 0);
    ll q2 = query(compress(a[i]+x)-1, 0);
    ll q3 = query(compress(a[i]+x)-1, 1);
    update(compress(a[i]), 0, q1+1);
    update(compress(a[i]+x), 1, max(q2, q3)+1);
  }
  cout << max(query(b.size()-1, 0), query(b.size()-1, 1));
}

• 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