Submission #674697

#	Time	Username	Problem	Language	Result	Execution time	Memory
674697		David1425	Sails (IOI07_sails)	C++17	100 / 100	91 ms	2516 KiB

sails

#include <bits/stdc++.h>
#ifndef CP_FENWICK_TREE
#define CP_FENWICK_TREE 1
#include <vector>
#include <algorithm>
namespace CP {
	template<typename T, typename OP=std::plus<T>>
	struct fenwick_tree {
		T base=0;
		std::vector<T> bit;
		int size;
		OP op;
		
		fenwick_tree(int n, T def=0) : size(n) {
			bit.resize(n+1);
			std::fill(bit.begin(), bit.end(), def);
		}
		
		void build(std::vector<T> vec) {
			int s = int(vec.size());
			for (int i = 1; i <= s; i++) {
				bit[i] = op(bit[i], vec[i-1]);
				int x = i + (i&-i);
				if (x <= s) bit[x] = op(bit[x], bit[i]);
			}
		}
		
		void upd(int i, T v) {
			for (; i <= size; i += i&-i) bit[i] = op(bit[i], v);
		}
		void iupd(int i, T v) {
			for (; i > 0; i -= i&-i) bit[i] = op(bit[i], v);
		}
		
		T qry(int i) {
			T r = base;
			for (; i > 0; i -= i&-i) r = op(r, bit[i]);
			return r;
		}
		T iqry(int i) {
			T r = base;
			for (; i <= size; i += i&-i) r = op(r, bit[i]);
			return r;
		}
	};
}
#endif

using namespace std;

typedef long long ll;

const int MM = 1e5+5;

CP::fenwick_tree<int> dif(MM);

int bs(int x) {
	int l = 0, r = MM-1;
	while (l < r) {
		int m = (l+r+1)/2;
		if (dif.iqry(m) >= x) l = m;
		else r = m-1;
	}
	return l;
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int n;
	cin >> n;
	pair<int,int> a[n];
	for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;
	sort(a,a+n);
	// for (auto i : a) cout << i.first << " " << i.second << "\n";
	
	for (auto i : a) {
		int h = i.first, k = i.second, x = h-k+1;
		// cout << h << " " << k << ": ";
		dif.iupd(h, 1);
		if (h == k) continue;
		else {
			int p = bs(dif.iqry(x)), q = bs(dif.iqry(x)+1);
			// cout << p << " " << q << "\n";
			dif.iupd(q,-1);
			dif.iupd(p+q-x+1,1);
			dif.iupd(p,-1);
		}
		
		// for (int i = 1; i <= a[n-1].first; i++) {
		// 	cout << dif.iqry(i) << " ";
		// }
		// cout << "\n";
	}
	
	ll ans = 0;
	for (int i = 1; i <= a[n-1].first; i++) {
		ll x = dif.iqry(i);
		ans += x*(x-1)/2;
	}
	cout << ans << '\n';
}

• 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