Submission #683324

#	Time	Username	Problem	Language	Result	Execution time	Memory
683324		badont	Sails (IOI07_sails)	C++17	70 / 100	102 ms	3784 KiB

sails

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

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using LL = long long;
using LD = long double;
using pii = pair<LL,LL>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

//var 
LL T;

template<typename T>
struct fen {
	vector<T> tr;
	LL mxn;

	fen(LL sz) {
		mxn = sz;
		tr.assign(sz + 5, 0);
	}

	void upd(LL g, T k) {
		assert(g != 0);
		for (; g <= mxn; g += g&-g)
			tr[g] += k;
	}

	T ge(LL g) {
		T res = 0;
		for (; g; g -= g&-g)
			res += tr[g];
		return res;
	}

	T rng(LL l, LL r) { return ge(r) - ge(l - 1); }

	//maxi and mini only work with positive numbers
	LL maxi(T k) {
		//max i such that ge(i) <= k.
		//log(n) vs log^2(n) binary search
		T running = 0; LL res = 0;
		LL lg = 32 - __builtin_clz(mxn);

		for (int i = lg; i>=0; i--) {
			if (res + (1LL << i) > mxn) continue;
			if (running + tr[res + (1LL << i)] > k) continue;
			running += tr[res + (1LL << i)];
			res += (1LL << i);
		}

		return res;
	}

	LL mini(T k) {
		//kth order statistic
		T running = 0; LL res = 0;
		LL lg = 32 - __builtin_clz(mxn);

		for (int i = lg; i>=0; i--) {
			if (res + (1LL << i) > mxn) continue;
			if (running + tr[res + (1LL << i)] >= k) continue;
			running += tr[res + (1LL << i)];
			res += (1LL << i);
		}

		return res + 1;
	}
};

void solve() {
	LL n; cin >> n;

	vector<pii> a(n);
	for (auto& [h, k] : a)
		cin >> h >> k;

	sort(all(a));
	const int M = 100000;
	fen<LL> hyz(M);

	auto range_update = [&](LL l, LL r, LL k) -> void {
		if (l > r) return;
		hyz.upd(l, k);
		hyz.upd(r + 1, -k);
	};

	auto high_end = [&](LL i) -> LL {
		LL val = hyz.ge(i);
		LL lo = i, hi = n, mid;
		while (lo < hi) {
			mid = (lo + hi + 1) >> 1;
			if (hyz.ge(mid) == val) lo = mid;
			else hi = mid - 1;
		}
		return lo;
	};

	auto low_end = [&](LL i) -> LL {
		LL val = hyz.ge(i);
		LL lo = 1, hi = i, mid;
		while (lo < hi) {
			mid = (lo + hi) >> 1;
			if (hyz.ge(mid) == val) hi = mid;
			else lo = mid + 1;
		}
		return lo;
	};

	//maintain nondecreasing
	for (auto [h, k] : a) {
		LL r = h;

		LL l = r - k + 1;
		LL ur = high_end(l) + 1;
		range_update(ur, r, 1);
		LL used = max(0LL, r - ur + 1);
		LL rem = k - used;

		LL ul = low_end(l);
		assert(rem <= ur - ul);
		range_update(ul, ul + rem - 1, 1);
	}		

	LL ans = 0;
	FOR (i, M) {
		LL x = hyz.ge(i);
		ans += ((x) * (x - 1)) / 2;
	}

	cout << ans << '\n';
}

int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);

	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();

	cout.flush();
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10