oj.uz

Submission #983357

# Submission time Handle Problem Language Result Execution time Memory
983357 2024-05-15T11:04:24 Z michified Sails (IOI07_sails) C++17
100 / 100
 40 ms 5716 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct mast_t {
	ll cnt, h;
};

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

	ll n, i, l, r, tmp;
	cin >> n;
	vector<mast_t> masts(n);
	for (i = 0; i < n; i++) cin >> masts[i].h >> masts[i].cnt;
	sort(masts.begin(), masts.end(), [](const mast_t& one, const mast_t& two){return one.h < two.h;});
	map<ll, ll> histo;
	mast_t mast;
	histo[0]++;
	histo[masts[0].cnt]--;
	for (i = 1; i < n; i++) {
		mast = masts[i];
		l = mast.h - mast.cnt;
		r = mast.h;
		histo[r]--;
		if (histo.find(l) != histo.end()) {
			histo[l]++;
			if (histo[l] == 0) histo.erase(l);
			continue;
		}
		auto lo = prev(histo.lower_bound(l)), hi = histo.upper_bound(l);
		lo -> second++;
		histo[lo -> first - l + hi -> first]--;
		if (lo -> second == 0) histo.erase(lo);
		hi -> second++;
		if (hi -> second == 0) histo.erase(hi);
	}
	auto cur = histo.begin();
	ll ans = 0, count = cur -> second;
	while (count > 0) {
		ans += count * (count - 1) * (next(cur) -> first - cur -> first);
		count += next(cur) -> second;
		cur = next(cur);
	}
	cout << ans / 2;
	return 0;
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:13:17: warning: unused variable 'tmp' [-Wunused-variable]
   13 |  ll n, i, l, r, tmp;
      |                 ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 504 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 452 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2952 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2732 KB Output is correct
2 Correct 26 ms 3412 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5716 KB Output is correct
2 Correct 21 ms 2396 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3936 KB Output is correct
2 Correct 19 ms 2904 KB Output is correct