#280469 (C++14) No.728 ギブ and テイク

提出ソース
結果

問題	No.728 ギブ and テイク
ユーザー	satanic
提出日時	2018-08-24 23:09:29
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	385 ms / 3,000 ms
コード長	20,363 bytes
コンパイル時間	1,650 ms
コンパイル使用メモリ	145,024 KB
実行使用メモリ	17,536 KB
最終ジャッジ日時	2024-06-23 09:09:15
合計ジャッジ時間	5,871 ms
ジャッジサーバーID （参考情報）	judge2 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	3 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	16 ms 5,376 KB
testcase_14	AC	27 ms 5,376 KB
testcase_15	AC	12 ms 5,376 KB
testcase_16	AC	24 ms 5,376 KB
testcase_17	AC	26 ms 5,376 KB
testcase_18	AC	284 ms 13,184 KB
testcase_19	AC	285 ms 13,824 KB
testcase_20	AC	337 ms 15,872 KB
testcase_21	AC	305 ms 14,336 KB
testcase_22	AC	111 ms 7,680 KB
testcase_23	AC	71 ms 6,016 KB
testcase_24	AC	216 ms 11,776 KB
testcase_25	AC	213 ms 11,648 KB
testcase_26	AC	106 ms 7,552 KB
testcase_27	AC	385 ms 17,536 KB
testcase_28	AC	311 ms 17,408 KB
testcase_29	AC	2 ms 5,376 KB
testcase_30	AC	1 ms 5,376 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	1 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
// need
#include <iostream>
#include <algorithm>

// data structure
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <complex>
//#include <deque>
#include <valarray>
#include <unordered_map>
#include <array>

// stream
//#include <istream>
//#include <sstream>
//#include <ostream>
#include <fstream>

// etc
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <chrono>
#include <random>
#include <numeric>

// input
#define INIT std::ios::sync_with_stdio(false);std::cin.tie(0);
#define VAR(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T& t) { std::cin >> t; }
template<typename First, typename...Rest>void MACRO_VAR_Scan(First& first, Rest&...rest) { std::cin >> first; MACRO_VAR_Scan(rest...); }
#define VEC_ROW(type, n, ...)std::vector<type> __VA_ARGS__;MACRO_VEC_ROW_Init(n, __VA_ARGS__); for(int i=0; i<n; ++i){MACRO_VEC_ROW_Scan(i, __VA_ARGS__);}
template<typename T> void MACRO_VEC_ROW_Init(int n, T& t) { t.resize(n); }
template<typename First, typename...Rest>void MACRO_VEC_ROW_Init(int n, First& first, Rest&...rest) { first.resize(n); MACRO_VEC_ROW_Init(n, rest...); }
template<typename T> void MACRO_VEC_ROW_Scan(int p, T& t) { std::cin >> t[p]; }
template<typename First, typename...Rest>void MACRO_VEC_ROW_Scan(int p, First& first, Rest&...rest) { std::cin >> first[p]; MACRO_VEC_ROW_Scan(p, rest...); }
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define MAT(type, c, m, n) std::vector<std::vector<type>> c(m, std::vector<type>(n));for(auto& r:c)for(auto& i:r)std::cin>>i;

// output
#define OUT(dist) std::cout<<(dist);
#define FOUT(n, dist) std::cout<<std::fixed<<std::setprecision(n)<<(dist);
#define SOUT(n, c, dist) std::cout<<std::setw(n)<<std::setfill(c)<<(dist);
#define SP std::cout<<" ";
#define TAB std::cout<<"\t";
#define BR std::cout<<"\n";
#define SPBR(i, n) std::cout<<(i + 1 == n ? '\n' : ' ');
#define ENDL std::cout<<std::endl;
#define FLUSH std::cout<<std::flush;
#define SHOW(dist) {std::cerr << #dist << "\t:" << (dist) << "\n";}
#define SHOWVECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOWVECTOR2(v) {std::cerr << #v << "\t:\n";for(const auto& xxx : v){for(const auto& yyy : xxx){std::cerr << yyy << " ";}std::cerr << "\n";}}
#define SHOWQUEUE(a) {auto tmp(a);std::cerr << #a << "\t:";while(!tmp.empty()){std::cerr << tmp.front() << " ";tmp.pop();}std::cerr << "\n";}

// utility
#define ALL(a) (a).begin(),(a).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define FORLL(i, a, n) for(ll i=ll(a);i<ll(n);++i)
#define RFORLL(i, a, n) for(ll i=ll(n)-1;i>=ll(a);--i)
#define REPLL(i, n) for(ll i=0;i<ll(n);++i)
#define RREPLL(i, n) for(ll i=ll(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
template<class T> inline T CHMAX(T& a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T CHMIN(T& a, const T b) { return a = (a > b) ? b : a; }
#define EXCEPTION(msg) throw std::string("Exception : " msg " [ in ") + __func__ + " : " + std::to_string(__LINE__) + " lines ]"
#define TRY(cond, msg) try {if (cond) EXCEPTION(msg);}catch (std::string s) {std::cerr << s << std::endl;}
void CHECKTIME(std::function<void()> f) { auto start = std::chrono::system_clock::now(); f(); auto end = std::chrono::system_clock::now(); auto res = std::chrono::duration_cast<std::chrono::nanoseconds>((end - start)).count(); std::cerr << "[Time:" << res << "ns  (" << res / (1.0e9) << "s)]\n"; }

// test
template<class T> std::vector<std::vector<T>> VV(int n, int m, T init = T()) {
	return std::vector<std::vector<T>>(n, std::vector<T>(m, init));
}
template<typename S, typename T>
std::ostream& operator<<(std::ostream& os, std::pair<S, T> p) {
	os << "(" << p.first << ", " << p.second << ")"; return os;
}

// type/const
//#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using PAIR = std::pair<int, int>;
using PAIRLL = std::pair<ll, ll>;
constexpr int INFINT = 1 << 30;                          // 1.07x10^ 9
constexpr int INFINT_LIM = (1LL << 31) - 1;              // 2.15x10^ 9
constexpr ll INFLL = 1LL << 60;                          // 1.15x10^18
constexpr ll INFLL_LIM = (1LL << 62) - 1 + (1LL << 62);  // 9.22x10^18
constexpr double EPS = 1e-10;
constexpr int MOD = 1000000007;
constexpr double PI = 3.141592653589793238462643383279;

template<class T, size_t N> void FILL(T(&a)[N], const T& val) { for (auto& x : a) x = val; }
template<class ARY, size_t N, size_t M, class T> void FILL(ARY(&a)[N][M], const T& val) { for (auto& b : a) FILL(b, val); }
template<class T> void FILL(std::vector<T>& a, const T& val) { for (auto& x : a) x = val; }
template<class ARY, class T> void FILL(std::vector<std::vector<ARY>>& a, const T& val) { for (auto& b : a) FILL(b, val); }

// ------------>8------------------------------------->8------------

// https://www.dropbox.com/sh/9lknvq4xay709cn/AAAX61z5W1m20MPkJ8V53l5ma/%23WaveletMatrix.cpp?dl=0
using namespace std;

typedef unsigned int u32;
inline int popcount(u32 x) {
	x = x - ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	return ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
//(k+1)番目の1の立っている位置(最下位から)を返す
//http://graphics.stanford.edu/~seander/bithacks.html#SelectPosFromMSBRank を参考にした
inline int select32(u32 x, int k) {
	u32 a, b, c; int t, s;
	a = (x & 0x55555555) + ((x >> 1) & 0x55555555);
	b = (a & 0x33333333) + ((a >> 2) & 0x33333333);
	c = (b & 0x0f0f0f0f) + ((b >> 4) & 0x0f0f0f0f);
	t = (c & 0xff) + ((c >> 8) & 0xff);
	s = 0;
	s += ((t - k - 1) & 128) >> 3; k -= t & ((t - k - 1) >> 8); //if(k >= t) s += 16, k -= t;
	t = (c >> s) & 0xf;
	s += ((t - k - 1) & 128) >> 4; k -= t & ((t - k - 1) >> 8); //if(k >= t) s += 8, k -= t;
	t = (b >> s) & 0x7;
	s += ((t - k - 1) & 128) >> 5; k -= t & ((t - k - 1) >> 8); //if(k >= t) s += 4, k -= t;
	t = (a >> s) & 0x3;
	s += ((t - k - 1) & 128) >> 6; k -= t & ((t - k - 1) >> 8); //if(k >= t) s += 2, k -= t;
	t = (x >> s) & 0x1;
	s += ((t - k - 1) & 128) >> 7; //if(k >= t) s += 1;
	return s;
}
//※静的なデータ構造
//constructした後setを何回か呼び、その後buildを呼んだ後にrank,selectが行える
struct FullyIndexableDictionary {
	static const int NOTFOUND = -1;
	static const int SELECTT_INTERVAL = 32; //SELECTT_INTERVAL >= 32
	int length, blockslength, count;
	vector<u32> blocks; vector<int> ranktable, selecttable0, selecttable1;
	FullyIndexableDictionary(int len) : length(len) {
		blocks.resize((blockslength = (len + 31) / 32) + 1);
	}
	inline void set(int i) { blocks[i / 32] |= 1 << i % 32; }
	void build() {
		if (length == 0) { count = 0; return; }
		ranktable.assign(blockslength + 1, 0);
		selecttable0.clear(); selecttable1.clear();
		int prev0 = 0, prev1 = 0, count0 = 0, count1 = 0;
		for (int i = 0; i < blockslength; i++) {
			ranktable[i] = count1;
			count1 += popcount(blocks[i]);
			count0 = 32 * (i + 1) - count1;
			if (prev1 < (count1 + SELECTT_INTERVAL - 1) / SELECTT_INTERVAL)
				selecttable1.push_back(i), prev1 = (count1 + SELECTT_INTERVAL - 1) / SELECTT_INTERVAL;
			if (prev0 < (count0 + SELECTT_INTERVAL - 1) / SELECTT_INTERVAL)
				selecttable0.push_back(i), prev0 = (count0 + SELECTT_INTERVAL - 1) / SELECTT_INTERVAL;
		}
		ranktable[blockslength] = count1;
		selecttable1.push_back(blockslength - 1);
		selecttable0.push_back(blockslength - 1);
		count = count1;
	}
	inline bool access(int pos) const {
		return blocks[pos / 32] >> pos % 32 & 1;
	}
	inline int rank(int pos) const {    //[0..pos)の1の個数
		int block_idx = pos / 32;
		return ranktable[block_idx] + popcount(blocks[block_idx] & (1U << pos % 32) - 1);
	}
	inline int rank(bool b, int pos) const { return b ? rank(pos) : pos - rank(pos); }
	inline int rank(bool b, int left, int right) const { return rank(b, right) - rank(b, left); }
	//O(log n)は重いよねえ。expect O(1) (たぶん) ならできるけど最悪ケースがなあ
	//あるいはメモリ4*32*n bytes でO(1)でもできるけど…ハッシュテーブルでうまくやればうまくできるか？
	template<bool b>
	int select(int k) const {   //(k+1)番目のbの位置
		if ((b ? count : length - count) <= k) return NOTFOUND;
		int selecttable_index = k / SELECTT_INTERVAL;
		int l = (b ? selecttable1 : selecttable0)[selecttable_index],
			u = (b ? selecttable1 : selecttable0)[selecttable_index + 1] + 1;   //ブロックを二分探索
		while (l + 1 < u) {
			int m = (l + u) / 2;
			((b ? ranktable[m] : m * 32 - ranktable[m]) <= k ? l : u) = m;
		}
		return l * 32 + select32(b ? blocks[l] : ~blocks[l], k - (b ? ranktable[l] : 32 * l - ranktable[l]));
	}
	inline int select(bool b, int k) const { return b ? select<true>(k) : select<false>(k); }
	inline int select(bool b, int k, int left) const { return select(b, rank(b, left) + k); }
};

/*
WaveletMatrix。たしかにこっちの方が「常に」使うべきな気がする
*/
inline unsigned int BITMASK(int i) {
	return (1 << i) - 1;
}
//※メモリ, 時間はだいたい支配的な部分のみ書く
//メモリ: (length * bitsize / 8) bytes
struct WaveletMatrix {
	typedef unsigned long long Val;
	static const int NOTFOUND = -1;
	static const Val UNDEFINED = Val(-1);
	static const int MAX_BITSIZE = 64;
	int length, bitsize; Val maxval;
	vector<FullyIndexableDictionary> dicts;
	vector<int> mids;
	//追加メモリ: (2 * length * sizeof Val) bytes
	//時間: bitsize * length * 大きめ
	void init(const vector<Val>& data) {
		length = data.size();
		maxval = *max_element(data.begin(), data.end());
		if (1ULL << (8 * sizeof(Val) - 1) <= maxval) bitsize = 8 * sizeof(Val);
		else for (bitsize = 0; Val(1) << bitsize <= maxval; bitsize++);
		dicts.assign(bitsize, length);
		mids.assign(bitsize, 0);
		vector<Val> datacurrent(data), datanext(length);
		for (int bit = 0; bit < bitsize; bit++) {
			int pos = 0;
			for (int i = 0; i < length; i++)
				if ((datacurrent[i] >> (bitsize - bit - 1) & 1) == 0)
					datanext[pos++] = datacurrent[i];
			mids[bit] = pos;
			for (int i = 0; i < length; i++)
				if ((datacurrent[i] >> (bitsize - bit - 1) & 1) != 0)
					dicts[bit].set(i), datanext[pos++] = datacurrent[i];
			dicts[bit].build();
			datacurrent.swap(datanext);
		}
	}
	Val access(int pos) const {
		Val val = 0;
		for (int bit = 0; bit < bitsize; bit++) {
			bool dir = dicts[bit].access(pos);
			val = val << 1 | (dir ? 1 : 0);
			pos = dicts[bit].rank(dir, pos);
			if (dir) pos += mids[bit];
		}
		return val;
	}
	int rank(Val val, int left, int right) const {
		if (val > maxval) return 0;
		for (int bit = 0; bit < bitsize; bit++) {
			bool dir = val >> (bitsize - bit - 1) & 1;
			left = dicts[bit].rank(dir, left), right = dicts[bit].rank(dir, right);
			if (dir) left += mids[bit], right += mids[bit];
		}
		return right - left;
	}
	int rank(Val val, int right) const { return rank(val, 0, right); }
	int rank_all(Val val, int left, int right, int& out_lt, int& out_gt) const {
		if (val > maxval) { out_lt = right - left; out_gt = 0; return 0; }
		out_lt = out_gt = 0;
		for (int bit = 0; bit < bitsize; bit++) {
			bool dir = val >> (bitsize - bit - 1) & 1;
			int leftcount = dicts[bit].rank(dir, left), rightcount = dicts[bit].rank(dir, right);
			(dir ? out_lt : out_gt) += (right - left) - (rightcount - leftcount);
			left = leftcount, right = rightcount;
			if (dir) left += mids[bit], right += mids[bit];
		}
		return right - left;
	}
	inline int rank_lt(Val val, int left, int right) const {
		int tmp_lt, tmp_gt;
		rank_all(val, left, right, tmp_lt, tmp_gt);
		return tmp_lt;
	}
	inline int rangefreq(int left, int right, Val bottom, Val up) {
		return rank_lt(up, left, right) - rank_lt(bottom, left, right);
	}
	//O(bitsize log length) (FID::selectがlog nで最悪の場合)
	int select(Val val, int k) const {
		if (val > maxval) return NOTFOUND;
		static int lefts[MAX_BITSIZE], rights[MAX_BITSIZE];
		int left = 0, right = length;
		for (int bit = 0; bit < bitsize; bit++) {
			lefts[bit] = left, rights[bit] = right;
			bool dir = val >> (bitsize - bit - 1) & 1;
			left = dicts[bit].rank(dir, left), right = dicts[bit].rank(dir, right);
			if (dir) left += mids[bit], right += mids[bit];
		}
		for (int bit = bitsize - 1; bit >= 0; bit--) {
			k = dicts[bit].select(val >> (bitsize - bit - 1) & 1, k, lefts[bit]);
			if (k == FullyIndexableDictionary::NOTFOUND || k >= rights[bit])
				return NOTFOUND;
			k -= lefts[bit];
		}
		return k;
	}
	int select(Val val, int k, int left) const { return select(val, k + rank(val, left)); }
	void quantile(int left, int right, int k, Val& out_val, int& out_k) const {
		if (right - left <= k) { out_val = UNDEFINED; out_k = NOTFOUND; return; }
		Val val = 0;
		for (int bit = 0; bit < bitsize; bit++) {
			int count = dicts[bit].rank(true, left, right);
			bool dir = k < count;
			val = val << 1 | (dir ? 1 : 0);
			if (!dir) k -= count;
			left = dicts[bit].rank(dir, left), right = dicts[bit].rank(dir, right);
			if (dir) left += mids[bit], right += mids[bit];
		}
		out_val = val; out_k = k;
	}
	struct IdxVal {
		int idx; Val val;
		IdxVal() {}
		IdxVal(int i, Val v) : idx(i), val(v) {}
	};
	inline Val quantile(int left, int right, int k) const {
		Val tmp_val; int tmp_k;
		quantile(left, right, k, tmp_val, tmp_k);
		return tmp_val;
	}
	inline IdxVal quantile_idxval(int left, int right, int k) const {
		Val tmp_val; int tmp_k;
		quantile(left, right, k, tmp_val, tmp_k);
		return IdxVal(select(tmp_val, tmp_k, left), tmp_val);
	}
	inline Val maximum(int left, int right) const { return quantile(left, right, 0); }
	inline Val minimum(int left, int right) const { return quantile(left, right, right - left - 1); }
	//区間がかぶってるとkとかがintより大きくなるよね
	void quantile_ranges(const vector<int>& lefts0, const vector<int>& rights0, int k, Val& out_val, int& out_k) const {
		int n = lefts0.size();
		int width = 0;
		for (int i = 0; i < n; i++) width += rights0[i] - lefts0[i];
		if (width <= k) { out_val = UNDEFINED; out_k = NOTFOUND; return; }
		static vector<int> lefts, rights; //自動変数だとメモリ確保の時間…と思ったけどこれだとどうだろう？
		lefts.assign(lefts0.begin(), lefts0.end());
		rights.assign(rights0.begin(), rights0.end());
		Val val = 0;
		for (int bit = 0; bit < bitsize; bit++) {
			int count = 0;
			for (int i = 0; i < n; i++) {
				count += dicts[bit].rank(true, lefts[i], rights[i]);
			}
			bool dir = k < count;
			val = val << 1 | (dir ? 1 : 0);
			if (!dir) k -= count;
			for (int i = 0; i < n; i++) {
				lefts[i] = dicts[bit].rank(dir, lefts[i]);
				rights[i] = dicts[bit].rank(dir, rights[i]);
				if (dir) lefts[i] += mids[bit], rights[i] += mids[bit];
			}
		}
		out_val = val; out_k = k;
	}
	//区間がかぶってるとバグる
	//区間がソートされていないとバグる
	inline IdxVal quantile_ranges_idxval(const vector<int>& lefts, const vector<int>& rights, int k) const {
		int n = lefts.size();
		Val tmp_val; int tmp_k;
		quantile_ranges(lefts, rights, k, tmp_val, tmp_k);
		for (int i = 0; i < n; i++) {
			if (tmp_k < rights[i] - lefts[i]) {
				return IdxVal(select(tmp_val, tmp_k, lefts[i]), tmp_val);
			}
			tmp_k -= rights[i] - lefts[i];
		}
		return IdxVal(NOTFOUND, UNDEFINED);
	}
	struct Range {
		int left, right;
		int bit; Val val;
		Range(int l, int r, int b, Val v) :
			left(l), right(r), bit(b), val(v) {}
	};
	//O(bitsize min(length, maxval) log min(length, maxval))?
	//priority_queueではやはり最悪ケースが…
	//でもランダムで適当(バラけすぎとかが無い)なデータに対しては結構速い
	template<typename F, typename FOut>
	int rectbfsk(const F& f, int left, int right, Val bottom, Val up, int k, FOut& out) const {
		int k0 = k;
		up = min(up, maxval + 1);
		priority_queue<Range, vector<Range>, F> q(f);
		q.push(Range(left, right, 0, 0));
		while (k && !q.empty()) {
			Range t = q.top(); q.pop();
			if (t.bit == bitsize) {
				f.pushvalues(out, t, k);
			}
			else {
				int leftcount = dicts[t.bit].rank(false, t.left);
				int rightcount = dicts[t.bit].rank(false, t.right);
				if (rightcount - leftcount != 0 &&
					bottom <= ((t.val << (bitsize - t.bit)) | BITMASK(bitsize - t.bit - 1)))
					q.push(Range(leftcount, rightcount, t.bit + 1, t.val << 1));
				if ((t.right - t.left) - (rightcount - leftcount) != 0 &&
					(((t.val << 1 | 1) << (bitsize - t.bit - 1))) < up) {
					q.push(Range(
						(t.left - leftcount) + mids[t.bit], (t.right - rightcount) + mids[t.bit],
						t.bit + 1, t.val << 1 | 1));
				}
			}
		}
		return k0 - k;
	}
	struct ValCount {
		Val val; int count;
		ValCount(Val v, int c) : val(v), count(c) {}
		ValCount() {}
	};
	struct FreqList {
		inline bool operator()(const Range& x, const Range& y) const {
			return x.right - x.left < y.right - y.left ||
				(x.right - x.left == y.right - y.left && x.val > y.val);
		}
		inline void pushvalues(vector<ValCount>& out, const Range& t, int& k) const {
			out.push_back(ValCount(t.val, t.right - t.left));
			k--;
		}
	};
	inline int topk(int left, int right, Val bottom, Val up, int k, vector<ValCount>& out) const {
		return rectbfsk<FreqList, vector<ValCount> >(FreqList(), left, right, bottom, up, k, out);
	}
	template<typename F, typename FOut>
	struct DfsInfo {
		const F& f;
		FOut& out;
		Val bottom, up;
		DfsInfo(const F& f_, FOut& o, Val b, Val u) : f(f_), out(o), bottom(b), up(u) {}
	};
	//O(min(k bitsize, min(length, maxval)))?
	//minじゃなくてもう少しなめらかな関数で上界得られそうだけど…kつの中で幅に入らない分は共有されるイメージ
	//でもO(k bitsize)はやはり心強いな。k=1ならO(bitsize)となるわけだし
	template<typename F, typename FOut>
	void rectdfsk_dfs(const DfsInfo<F, FOut>& info, int bit, Val val, int left, int right, int& k) const {
		if (bit == bitsize) {
			info.f.pushvalues(info.out, val, right - left, k);
			return;
		}
		int leftcount = dicts[bit].rank(left);
		int rightcount = dicts[bit].rank(right);
		if (F::MAXF) {
			if (k > 0 && rightcount - leftcount != 0 && (((val << 1 | 1) << (bitsize - bit - 1)) < info.up))
				rectdfsk_dfs<F, FOut>(info, bit + 1, val << 1 | 1, leftcount + mids[bit], rightcount + mids[bit], k);
			if (k > 0 && (right - left) - (rightcount - leftcount) != 0 && (info.bottom <= ((val << (bitsize - bit)) | BITMASK(bitsize - bit - 1))))
				rectdfsk_dfs<F, FOut>(info, bit + 1, val << 1, left - leftcount, right - rightcount, k);
		}
		else {
			if (k > 0 && (right - left) - (rightcount - leftcount) != 0 &&
				(info.bottom <= ((val << (bitsize - bit)) | BITMASK(bitsize - bit - 1))))
				rectdfsk_dfs<F, FOut>(info, bit + 1, val << 1, left - leftcount, right - rightcount, k);
			if (k > 0 && rightcount - leftcount != 0 && (((val << 1 | 1) << (bitsize - bit - 1)) < info.up))
				rectdfsk_dfs<F, FOut>(info, bit + 1, val << 1 | 1, leftcount + mids[bit], rightcount + mids[bit], k);
		}
	}
	template<bool maxf>
	struct MinMaxList {
		enum { MAXF = maxf };
		inline void pushvalues(vector<ValCount>& out, Val val, int count, int& k) const {
			out.push_back(ValCount(val, min(k, count)));
			k -= min(k, count);
		}
	};
	template<typename F, typename FOut>
	int rectdfsk(const F& f, int left, int right, Val bottom, Val up, int k, FOut& out) const {
		rectdfsk_dfs<F, FOut>(DfsInfo<F, FOut>(f, out, bottom, up), 0, 0, left, right, k);
		return k;
	}
	template<bool maxf>
	int rectminmaxk(int left, int right, Val bottom, Val up, int k, vector<ValCount>& out) const {
		return rectdfsk<MinMaxList<maxf>, vector<ValCount> >(MinMaxList<maxf>(), left, right, bottom, up, k, out);
	}
};

signed main() {
	INIT;

	VAR(int, n);
	VEC(int, a, n);
	VEC_ROW(int, n, L, R);

	std::vector<unsigned long long> b(n);
	REP(i, n) b[i] = a[i] + R[i];
	WaveletMatrix wav;
	wav.init(b);

	ll cnt = 0;
	FOR(j, 1, n) {
		int i = std::lower_bound(ALL(a), a[j] - L[j]) - a.begin();
		if (i >= j) continue;

		// [i, j)をチェック
		cnt += wav.rangefreq(i, j, a[j], INFINT_LIM);
	}
	OUT(cnt)BR;

	return 0;
}
yukicoder

結果

テストケース

ソースコード
