結果

問題 No.2808 Concentration
ユーザー shobonvipshobonvip
提出日時 2024-07-12 22:22:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 6,891 bytes
コンパイル時間 7,146 ms
コンパイル使用メモリ 397,328 KB
実行使用メモリ 150,728 KB
最終ジャッジ日時 2024-07-12 22:23:41
合計ジャッジ時間 56,557 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 AC 1,343 ms
150,452 KB
testcase_03 AC 1,355 ms
146,084 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 490 ms
61,344 KB
testcase_08 AC 179 ms
26,740 KB
testcase_09 AC 7 ms
6,944 KB
testcase_10 AC 750 ms
95,176 KB
testcase_11 AC 730 ms
90,108 KB
testcase_12 AC 346 ms
41,776 KB
testcase_13 AC 1,091 ms
135,836 KB
testcase_14 AC 152 ms
23,444 KB
testcase_15 AC 1,044 ms
130,864 KB
testcase_16 AC 1,019 ms
128,596 KB
testcase_17 AC 1,287 ms
142,476 KB
testcase_18 AC 1,162 ms
147,764 KB
testcase_19 AC 576 ms
71,500 KB
testcase_20 AC 1,085 ms
142,188 KB
testcase_21 AC 955 ms
124,140 KB
testcase_22 WA -
testcase_23 AC 637 ms
83,324 KB
testcase_24 AC 1,077 ms
133,184 KB
testcase_25 AC 567 ms
72,084 KB
testcase_26 AC 1,146 ms
131,644 KB
testcase_27 AC 1,224 ms
147,804 KB
testcase_28 AC 1,211 ms
146,472 KB
testcase_29 AC 1,154 ms
146,296 KB
testcase_30 AC 1,199 ms
147,124 KB
testcase_31 AC 1,128 ms
147,208 KB
testcase_32 AC 1,157 ms
147,012 KB
testcase_33 AC 1,248 ms
146,408 KB
testcase_34 AC 1,149 ms
147,012 KB
testcase_35 AC 1,182 ms
147,556 KB
testcase_36 AC 1,135 ms
146,888 KB
testcase_37 AC 1,222 ms
147,528 KB
testcase_38 AC 1,176 ms
146,756 KB
testcase_39 AC 1,183 ms
148,268 KB
testcase_40 AC 1,180 ms
147,388 KB
testcase_41 AC 1,163 ms
146,548 KB
testcase_42 AC 1,218 ms
147,560 KB
testcase_43 AC 1,258 ms
146,988 KB
testcase_44 AC 1,206 ms
148,016 KB
testcase_45 AC 1,178 ms
147,516 KB
testcase_46 AC 1,184 ms
147,612 KB
testcase_47 AC 2 ms
6,944 KB
testcase_48 AC 2 ms
6,944 KB
testcase_49 AC 2 ms
6,944 KB
testcase_50 AC 2 ms
6,944 KB
testcase_51 AC 2 ms
6,940 KB
testcase_52 AC 2 ms
6,940 KB
testcase_53 AC 2 ms
6,944 KB
testcase_54 AC 2 ms
6,944 KB
testcase_55 AC 2 ms
6,940 KB
testcase_56 AC 2 ms
6,940 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){
		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