oj.uz

Submission #86583

# Submission time Handle Problem Language Result Execution time Memory
86583 2018-11-26T17:26:34 Z JustInCase Sails (IOI07_sails) C++17
100 / 100
 109 ms 8588 KB 
#include <bits/stdc++.h>

const int32_t MAX_N = 1e5;
const int32_t MAX_H = 1e5;

class IndexTree {
private:
	int32_t data[MAX_H + 5];

public:
	void Add(int32_t ind, int32_t val) {
		while(ind <= MAX_H) {
			data[ind] += val;
			ind += (ind & (-ind));
		}
	}

	int32_t Query(int32_t ind) {
		int32_t ans = 0;
		
		while(ind > 0) {
			ans += data[ind];
			ind -= (ind & (-ind));
		}

		return ans;
	}
};

IndexTree indTree;
std::pair< int32_t, int32_t > masts[MAX_N + 5];

int32_t BinarySearchLow(int32_t low, int32_t high, int32_t ind) {
	int32_t ans = low, sumToInd = indTree.Query(ind);

	while(low <= high) {
		int32_t mid = (low + high) / 2;

		if(indTree.Query(mid) != sumToInd) {
			ans = mid + 1;
			low = mid + 1;
		}
		else {
			high = mid - 1;
		}
	}

	return ans;
}

int32_t BinarySearchHigh(int32_t low, int32_t high, int32_t ind) {
	int32_t ans = high + 1, sumToInd = indTree.Query(ind);

	while(low <= high) {
		int32_t mid = (low + high) / 2;

		if(indTree.Query(mid) != sumToInd) {
			ans = mid;
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}

	return ans;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int32_t n;
	std::cin >> n;

	for(int32_t i = 0; i < n; i++) {
		std::cin >> masts[i].first >> masts[i].second;
	}

	std::sort(masts, masts + n);
	
	for(int32_t i = 0; i < n; i++) {
		if(i != 0 && masts[i - 1].first != masts[i].first) {
			indTree.Add(masts[i - 1].first + 1, -indTree.Query(masts[i - 1].first));
		}

		int32_t ind = masts[i].first - masts[i].second + 1;

		if(ind != 1 && indTree.Query(ind) == indTree.Query(ind - 1)) {
			int32_t low = BinarySearchLow(1, ind - 1, ind);	
			int32_t high = BinarySearchHigh(ind + 1, masts[i].first, ind);
		
			int32_t aux = low + high - ind - 1;
			
			indTree.Add(low, 1);
			indTree.Add(aux + 1, -1);
			
			if(high != masts[i].first + 1) {
				indTree.Add(high, 1);
			}
		}
		else {
			indTree.Add(ind, 1);
		}
	}

	int64_t ans = 0;
	for(int32_t i = 1; i <= masts[n - 1].first; i++) {
		int32_t curr = indTree.Query(i);
		
		ans += (int64_t) curr * (curr - 1) / 2;
	}
	
	std::cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1060 KB Output is correct
2 Correct 24 ms 1436 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1732 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 2616 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 3852 KB Output is correct
2 Correct 74 ms 4784 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 5964 KB Output is correct
2 Correct 62 ms 6616 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 7832 KB Output is correct
2 Correct 89 ms 8588 KB Output is correct