結果

問題 No.2808 Concentration
ユーザー shobonvipshobonvip
提出日時 2024-07-12 22:26:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 7,130 bytes
コンパイル時間 6,427 ms
コンパイル使用メモリ 397,756 KB
実行使用メモリ 155,820 KB
最終ジャッジ日時 2024-07-12 22:27:22
合計ジャッジ時間 60,843 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 1,439 ms
155,604 KB
testcase_03 AC 1,467 ms
154,396 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 547 ms
64,000 KB
testcase_08 AC 192 ms
27,744 KB
testcase_09 AC 7 ms
5,376 KB
testcase_10 AC 811 ms
99,312 KB
testcase_11 AC 768 ms
93,920 KB
testcase_12 AC 369 ms
43,644 KB
testcase_13 AC 1,206 ms
141,592 KB
testcase_14 AC 159 ms
24,392 KB
testcase_15 AC 1,162 ms
136,260 KB
testcase_16 AC 1,096 ms
131,708 KB
testcase_17 AC 1,384 ms
148,420 KB
testcase_18 AC 1,225 ms
152,804 KB
testcase_19 AC 604 ms
74,528 KB
testcase_20 AC 1,168 ms
145,792 KB
testcase_21 AC 1,128 ms
127,896 KB
testcase_22 WA -
testcase_23 AC 658 ms
86,880 KB
testcase_24 AC 1,223 ms
138,352 KB
testcase_25 AC 634 ms
75,132 KB
testcase_26 AC 1,268 ms
137,220 KB
testcase_27 AC 1,380 ms
153,896 KB
testcase_28 AC 1,323 ms
153,000 KB
testcase_29 AC 1,308 ms
152,620 KB
testcase_30 AC 1,332 ms
152,232 KB
testcase_31 AC 1,280 ms
153,380 KB
testcase_32 AC 1,263 ms
153,256 KB
testcase_33 AC 1,366 ms
152,872 KB
testcase_34 AC 1,325 ms
153,128 KB
testcase_35 AC 1,340 ms
153,892 KB
testcase_36 AC 1,310 ms
153,128 KB
testcase_37 AC 1,376 ms
153,940 KB
testcase_38 AC 1,326 ms
153,000 KB
testcase_39 AC 1,391 ms
154,156 KB
testcase_40 AC 1,293 ms
153,648 KB
testcase_41 AC 1,364 ms
152,872 KB
testcase_42 AC 1,339 ms
153,704 KB
testcase_43 AC 1,393 ms
153,320 KB
testcase_44 AC 1,368 ms
154,540 KB
testcase_45 AC 1,376 ms
153,768 KB
testcase_46 AC 1,295 ms
153,892 KB
testcase_47 AC 2 ms
5,376 KB
testcase_48 AC 2 ms
5,376 KB
testcase_49 AC 2 ms
5,376 KB
testcase_50 AC 2 ms
5,376 KB
testcase_51 AC 2 ms
5,376 KB
testcase_52 AC 2 ms
5,376 KB
testcase_53 AC 2 ms
5,376 KB
testcase_54 AC 2 ms
5,376 KB
testcase_55 AC 2 ms
5,376 KB
testcase_56 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

//* ATCODER
#include<atcoder/all>
using namespace atcoder;
typedef modint998244353 mint;
//*/

/* BOOST MULTIPRECISION
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
//*/

typedef long long ll;

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)

template <typename T> bool chmin(T &a, const T &b) {
	if (a <= b) return false;
	a = b;
	return true;
}

template <typename T> bool chmax(T &a, const T &b) {
	if (a >= b) return false;
	a = b;
	return true;
}

template <typename T> T max(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]);
	return ret;
}

template <typename T> T min(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]);
	return ret;
}

template <typename T> T sum(vector<T> &a){
	T ret = 0;
	for (int i=0; i<(int)a.size(); i++) ret += a[i];
	return ret;
}
// defcomp
template <typename T>
vector<T> compress(vector<T> &X) {
	vector<T> vals = X;
	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());
	return vals;
}
// -----


// importbisect
template <typename T>
int bisect_left(vector<T> &X, T v){
	return lower_bound(X.begin(), X.end(), v) - X.begin();
}

template <typename T>
int bisect_right(vector<T> &X, T v){
	return upper_bound(X.begin(), X.end(), v) - X.begin();
}
// -----


//https://nyaannyaan.github.io/library/verify/verify-yosupo-ds/yosupo-point-add-rectangle-sum-wm.test.cpp
#include <immintrin.h>
//

struct bit_vector {
  using u32 = uint32_t;
  using i64 = int64_t;
  using u64 = uint64_t;

  static constexpr u32 w = 64;
  vector<u64> block;
  vector<u32> count;
  u32 n, zeros;

  inline u32 get(u32 i) const { return u32(block[i / w] >> (i % w)) & 1u; }
  inline void set(u32 i) { block[i / w] |= 1LL << (i % w); }

  bit_vector() {}
  bit_vector(int _n) { init(_n); }
  __attribute__((optimize("O3,unroll-loops"))) void init(int _n) {
    n = zeros = _n;
    block.resize(n / w + 1, 0);
    count.resize(block.size(), 0);
  }

  __attribute__((target("popcnt"))) void build() {
    for (u32 i = 1; i < block.size(); ++i)
      count[i] = count[i - 1] + _mm_popcnt_u64(block[i - 1]);
    zeros = rank0(n);
  }

  inline u32 rank0(u32 i) const { return i - rank1(i); }

  __attribute__((target("bmi2,popcnt"))) inline u32 rank1(u32 i) const {
    return count[i / w] + _mm_popcnt_u64(_bzhi_u64(block[i / w], i % w));
  }
};

template <typename S, typename T>
struct WaveletMatrix {
  using u32 = uint32_t;
  using i64 = int64_t;
  using u64 = uint64_t;

  struct BIT {
    u32 N;
    vector<T> data;

    BIT() = default;
    BIT(int size) { init(size); }

    void init(int size) {
      N = size;
      data.assign(N + 1, 0);
    }

    __attribute__((target("bmi"))) void add(u32 k, T x) {
      for (++k; k <= N; k += _blsi_u32(k)) data[k] += x;
    }

    __attribute__((target("bmi"))) T sum(u32 k) const {
      T ret = T();
      for (; k; k = _blsr_u32(k)) ret += data[k];
      return ret;
    }

    __attribute__((target("bmi"))) T sum(int l, int r) const {
      T ret = T();
      while (l != r) {
        if (l < r) {
          ret += data[r];
          r = _blsr_u32(r);
        } else {
          ret -= data[l];
          l = _blsr_u32(l);
        }
      }
      return ret;
    }
  };

  using P = pair<S, S>;
  int n, lg;
  vector<bit_vector> bv;
  vector<BIT> bit;
  vector<P> ps;
  vector<S> ys;

  WaveletMatrix() {}

  void add_point(S x, S y) {
    ps.emplace_back(x, y);
    ys.emplace_back(y);
  }

  __attribute__((optimize("O3"))) void build() {
    sort(begin(ps), end(ps));
    ps.erase(unique(begin(ps), end(ps)), end(ps));
    n = ps.size();
    sort(begin(ys), end(ys));
    ys.erase(unique(begin(ys), end(ys)), end(ys));
    vector<u32> cur(n), nxt(n);
    for (int i = 0; i < n; ++i) cur[i] = yid(ps[i].second);
    lg = __lg(max(n, 1)) + 1;
    bv.assign(lg, n);
    bit.assign(lg, n);
    for (int h = lg - 1; h >= 0; --h) {
      for (int i = 0; i < n; ++i)
        if ((cur[i] >> h) & 1) bv[h].set(i);
      bv[h].build();
      array<decltype(begin(nxt)), 2> it{begin(nxt), begin(nxt) + bv[h].zeros};
      for (int i = 0; i < n; ++i) *it[bv[h].get(i)]++ = cur[i];
      swap(cur, nxt);
    }
  }

  int xid(S x) const {
    return lower_bound(
               begin(ps), end(ps), make_pair(x, S()),
               [](const P& a, const P& b) { return a.first < b.first; }) -
           begin(ps);
  }

  int yid(S y) const { return lower_bound(begin(ys), end(ys), y) - begin(ys); }

  void add(S x, S y, T val) {
    int i = lower_bound(begin(ps), end(ps), P{x, y}) - begin(ps);
    for (int h = lg - 1; h >= 0; --h) {
      int i0 = bv[h].rank0(i);
      if (bv[h].get(i))
        i += bv[h].zeros - i0;
      else
        i = i0;
      bit[h].add(i, val);
    }
  }

  T sum(int l, int r, u32 upper) const {
    T res = 0;
    for (int h = lg; h--;) {
      int l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
      if ((upper >> h) & 1) {
        res += bit[h].sum(l0, r0);
        l += bv[h].zeros - l0;
        r += bv[h].zeros - r0;
      } else {
        l = l0, r = r0;
      }
    }
    return res;
  }

  T sum(S L, S D, S R, S U) const {
    int l = xid(L), r = xid(R);
    return sum(l, r, yid(U)) - sum(l, r, yid(D));
  }
};
int main(){
	int n; cin >> n;
	ll s, h; cin >> s >> h;
	vector<ll> x(n), y(n), z(n);
	vector<ll> v;
	rep(i,0,n){
		cin >> x[i] >> y[i] >> z[i];
		v.push_back(x[i]);
		v.push_back(x[i]+s+h);

		v.push_back(y[i]-s);
		v.push_back(y[i]+h);

		v.push_back(y[i]-s-h);
		v.push_back(y[i]);
	}

	vector<pair<ll,int>> p;
	rep(i,0,n){
		p.push_back(pair(x[i], i));
	}
	sort(p.begin(), p.end());

	vector<ll> px(n);
	rep(i,0,n){
		px[i] = p[i].first;
	}

	WaveletMatrix<ll,ll> wm;
	rep(i,0,n){
		wm.add_point(i, y[p[i].second]);
	}

	wm.build();
	rep(i,0,n){
		wm.add(i, y[p[i].second], z[p[i].second]);
	}

	v = compress(v);
	int m = v.size();
	vector ikeru(m, vector<pair<int, ll>>(0));
	rep(i,0,m-1){
		ikeru[i+1].push_back(pair(i, 0));
	}

	rep(i,0,n){
		int lft = bisect_left(v, x[i]);
		int rgt = bisect_left(v, x[i]+s+h);
		int lx = bisect_left(px, x[i]);
		ll vv = wm.sum(lx, x[i], n, x[i]+s+1);
		ikeru[rgt].push_back(pair(lft, vv));
	}

	
	rep(i,0,n){
		if (y[i] - x[i] <= s){
			int lft = bisect_left(v, x[i]);
			int rgt = bisect_left(v, y[i]+h);
			int lx = bisect_left(px, x[i]);
			ll vv = wm.sum(lx, x[i], n, y[i]+1);
			ikeru[rgt].push_back(pair(lft, vv));
		}
	}

	rep(i,0,n){
		int lft = bisect_left(v, y[i]-s);
		int rgt = bisect_left(v, y[i]+h);
		int lx = bisect_left(px, y[i]-s);
		ll vv = wm.sum(lx, y[i]-s, n, y[i]+1);
		ikeru[rgt].push_back(pair(lft, vv));
	}

	rep(i,0,n){
		int lft = bisect_left(v, y[i]-s-h);
		int rgt = bisect_left(v, y[i]);
		int lx = bisect_left(px, y[i]-s-h);
		ll vv = wm.sum(lx, y[i]-s-h, n, y[i]-h+1);
		ikeru[rgt].push_back(pair(lft, vv));
	}

	vector<ll> dp(m);
	rep(i,0,m){
		for (auto [j, x]: ikeru[i]){
			chmax(dp[i], dp[j] + x);
		}
	}
	cout << max(dp) << endl;
}
0