oj.uz

Submission #674697

# Submission time Handle Problem Language Result Execution time Memory
674697 2022-12-25T23:06:54 Z David1425 Sails (IOI07_sails) C++17
100 / 100
 91 ms 2516 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 728 KB Output is correct
2 Correct 3 ms 724 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 724 KB Output is correct
2 Correct 27 ms 1236 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 852 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 980 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 1236 KB Output is correct
2 Correct 62 ms 2184 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 1364 KB Output is correct
2 Correct 56 ms 2004 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 1492 KB Output is correct
2 Correct 81 ms 2516 KB Output is correct