結果

問題 No.2520 L1 Explosion
ユーザー binapbinap
提出日時 2023-10-27 23:28:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 43 ms / 2,000 ms
コード長 2,721 bytes
コンパイル時間 5,451 ms
コンパイル使用メモリ 276,032 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-27 23:28:58
合計ジャッジ時間 6,237 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 41 ms
4,348 KB
testcase_07 AC 14 ms
4,348 KB
testcase_08 AC 42 ms
4,348 KB
testcase_09 AC 41 ms
4,348 KB
testcase_10 AC 42 ms
4,348 KB
testcase_11 AC 43 ms
4,348 KB
testcase_12 AC 42 ms
4,348 KB
testcase_13 AC 41 ms
4,348 KB
testcase_14 AC 42 ms
4,348 KB
testcase_15 AC 4 ms
4,348 KB
testcase_16 AC 31 ms
4,348 KB
testcase_17 AC 20 ms
4,348 KB
testcase_18 AC 22 ms
4,348 KB
testcase_19 AC 18 ms
4,348 KB
testcase_20 AC 3 ms
4,348 KB
testcase_21 AC 29 ms
4,348 KB
testcase_22 AC 5 ms
4,348 KB
testcase_23 AC 4 ms
4,348 KB
testcase_24 AC 25 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long>> vvl;
typedef long double ld;
typedef pair<int, int> P;

template <int m>
std::ostream& operator<<(std::ostream& os, const atcoder::static_modint<m>& a) {os << a.val(); return os;}
template<typename T>
istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;}
template <typename T>
ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;}

// Coodinate Compression
// https://youtu.be/fR3W5IcBGLQ?t=8550
template<typename T=int>
struct CC {
  bool initialized;
  vector<T> xs;
  CC(): initialized(false) {}
  void add(T x) { xs.push_back(x);}
  void init() {
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end());
    initialized = true;
  }
  int operator()(T x) {
    if (!initialized) init();
    return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
  }
  T operator[](int i) {
    if (!initialized) init();
    return xs[i];
  }
  int size() {
    if (!initialized) init();
    return xs.size();
  }
};

using mint = modint998244353;

int main(){
	int n;
	ll m;
	cin >> n >> m;
	vl x(n), y(n), h(n);
	rep(i, n) cin >> x[i] >> y[i] >> h[i];
	CC<ll> cc_s, cc_t;
	rep(i, n) cc_s.add((x[i] - (m - h[i])) + y[i]);
	rep(i, n) cc_s.add((x[i] + (m - h[i])) + y[i]);
	rep(i, n) cc_t.add((x[i] - (m - h[i])) - y[i]);
	rep(i, n) cc_t.add((x[i] + (m - h[i])) - y[i]);
	int ks = cc_s.size();
	int kt = cc_t.size();
	vector<vector<tuple<int, int, int>>> event(kt);
	rep(i, n){
		event[cc_t((x[i] - (m - h[i])) - y[i])].emplace_back(+1, cc_s(x[i] - (m - h[i]) + y[i]), cc_s(x[i] + (m - h[i]) + y[i]));
		event[cc_t((x[i] + (m - h[i])) - y[i])].emplace_back(-1, cc_s(x[i] - (m - h[i]) + y[i]), cc_s(x[i] + (m - h[i]) + y[i]));
	}
	/*
	cout << cc_s.xs;
	cout << cc_t.xs;
	*/
	vi memo(ks);
	vector<mint> ans(n + 1);
	rep(t, kt){
		auto& v = event[t];
		if(t > 0){
			rep(s, ks - 1){
				ans[memo[s]] += (cc_t[t] - cc_t[t - 1]) * (cc_s[s + 1] - cc_s[s]);
			}
		}
//		cout << v.size() << "\n";
		for(auto [parity, from, to] : v){
			for(int s = from; s < to; s++){
				memo[s] += parity;
			}
		}
		/*
		cout << memo;
		cout << ans;
		cout << "\n";
		*/
	}
	for(int i = 1; i <= n; i++){
		cout << ans[i] / 2<< "\n";
	}
	return 0;
}
0