#994371 (C++17) No.2808 Concentration

提出ソース
結果

問題	No.2808 Concentration
コンテスト
ユーザー	shobonvip
提出日時	2024-07-12 22:22:31
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	WA
実行時間	-
コード長	6,891 bytes
コンパイル時間	6,636 ms
コンパイル使用メモリ	396,280 KB
最終ジャッジ日時	2025-02-22 04:24:33
ジャッジサーバーID （参考情報）	judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 54 WA * 3
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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;
}
yukicoder

結果

ソースコード
