Submission #1162272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162272		DangKhoizzzz	Sails (IOI07_sails)	C++20	100 / 100	84 ms	2372 KiB

sails

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

// BeginCodeSnip{Binary Indexed Tree (from the module)}
template <class T> class BIT {
  private:
	int size;
	vector<T> bit;
	vector<T> arr;

  public:
	BIT(int size) : size(size), bit(size + 1), arr(size) {}

	void set(int ind, T val) { add(ind, val - arr[ind]); }

	void add(int ind, T val) {
		arr[ind] += val;
		ind++;
		for (; ind <= size; ind += ind & -ind) { bit[ind] += val; }
	}

	T pref_sum(int ind) {
		ind++;
		T total = 0;
		for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
		return total;
	}
};
// EndCodeSnip

int main() {
	int n;
	cin >> n;
	vector<int> h(n), k(n);
	for (int i = 0; i < n; i++) { cin >> h[i] >> k[i]; }

	vector<int> ord(n);
	iota(begin(ord), end(ord), 0);
	sort(begin(ord), end(ord), [&](int i, int j) -> bool { return h[i] < h[j]; });

	const int max_h = *max_element(begin(h), end(h));
	BIT<int> bit(max_h + 1);

	/** @return first index with bit.pref_sum(i) < val */
	const auto first_val = [&](int val, int high) {
		int low = 0;
		while (low < high) {
			int mid = low + (high - low) / 2;
			int cur_val = bit.pref_sum(mid);
			(cur_val < val) ? high = mid : low = mid + 1;
		}
		return low;
	};

	for (int i : ord) {
		int last = h[i] - k[i];
		int val = bit.pref_sum(last);
		int idx_1 = first_val(val, h[i]);
		int idx_2 = first_val(val + 1, h[i]);
		bit.add(idx_1, 1);
		bit.add(h[i], -1);
		bit.add(idx_2, 1);
		bit.add(idx_2 + k[i] - (h[i] - idx_1), -1);
	}

	ll res = 0;
	for (int i = 0; i < max_h; i++) {
		int sail_num = bit.pref_sum(i);
		res += 1ll * sail_num * (sail_num - 1) / 2;
	}

	cout << res << endl;
}

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