oj.uz

Submission #145900

# Submission time Handle Problem Language Result Execution time Memory
145900 2019-08-21T10:44:06 Z Sorting Sails (IOI07_sails) C++14
30 / 100
 94 ms 1528 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 - 7;

	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);

	int ans = 0;

	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);
	}

	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 4 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 504 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 312 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 632 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 988 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 1360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 1528 KB Output isn't correct
2 Halted 0 ms 0 KB -