oj.uz

Submission #145903

# Submission time Handle Problem Language Result Execution time Memory
145903 2019-08-21T10:46:47 Z Sorting Sails (IOI07_sails) C++14
100 / 100
 94 ms 1508 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 7;

int fenwick[MAXN];

void update(int idx, int val){
	for(; idx < MAXN; idx += (idx & -idx)){
		fenwick[idx] += val;
	}
}

int query(int idx){
	int ret = 0;

	for(; idx >= 1; idx -= (idx & -idx)){
		ret += fenwick[idx];
	}

	return ret;
}

int n;
pair<int, int> a[MAXN]; //height, number of sails

int binary_search(int val){
	int l = 1, r = MAXN - 4;

	while(l != r){
		int mid = (l + r) >> 1;

		//cout << l << " " << r << endl;

		if(query(mid) > val){
			l = mid + 1;
		}
		else{
			r = mid;
		}
	}

	return l;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;

	for(int i = 0; i < n; ++i){
		cin >> a[i].first >> a[i].second;
	}

	sort(a, a + n);

	

	for(int i = 0; i < n; ++i){
		//cout << i << endl;
		if(a[i].first == a[i].second){
			update(1, 1);
			update(a[i].first + 1, -1);
			continue;
		}

		int val = query(a[i].first - a[i].second + 1);
		//cout << a[i].first << " " << a[i].second << " " << val << endl; 
		int l = binary_search(val), r = min(binary_search(val - 1) - 1, a[i].first);

		//cout << l << "  - " << r << endl;

		update(r + 1, 1);
		update(a[i].first + 1, -1);

		int cnt = r - (a[i].first - a[i].second + 1) + 1;

		update(l, 1);
		update(l + cnt, -1);
	}

	long long ans = 0;

	for(int i = 1; i <= MAXN - 4; i++){
		long long curr = query(i);

		ans += (long long)curr * (curr - 1ll) / 2ll;
	}

	cout << ans << "\n";

	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 380 KB Output is correct
2 Correct 4 ms 788 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 508 KB Output is correct
2 Correct 24 ms 632 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 760 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 988 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 1364 KB Output is correct
2 Correct 67 ms 1272 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 1448 KB Output is correct
2 Correct 63 ms 1352 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 1508 KB Output is correct
2 Correct 66 ms 1220 KB Output is correct