oj.uz

Submission #587435

# Submission time Handle Problem Language Result Execution time Memory
587435 2022-07-01T21:15:07 Z GusterGoose27 Sails (IOI07_sails) C++11
35 / 100
 36 ms 5332 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
//typedef long double ld;
typedef pair<ll, ll> pil;
//typedef pair<ld, ll> pdi;

const ll MAXN = 1e5;
ll sails_avail[MAXN];
ll sails_above[MAXN];
pil polls[MAXN];
ll sortable[MAXN];

ll n;

struct comp {
	bool operator()(const ll &a, const ll &b) {
		if (polls[a].second*polls[b].first == polls[b].second*polls[a].first) return polls[a].first > polls[b].first;
		return polls[a].second*polls[b].first < polls[b].second*polls[a].first;
	}
} comp;

ll area(pil &a, pil &b, pil &c) {
	ll aval = a.first*b.second+b.first*c.second+c.first*a.second;
	ll bval = a.second*b.first+b.second*c.first+c.second*a.first;
	return abs(aval-bval);
}

bool contained(pil &a, pil &b, pil &c, pil &p) {
	return (area(a, b, p) + area(a, c, p) + area(b, c, p) == area(a, b, c));
}

ll c2(ll a) {
	return a*(a-1)/2;
}

ll ineff(ll y, ll x) {
	ll per = y/x;
	ll numgreat = y-x*per;
	return (x-numgreat)*c2(per)+numgreat*c2(per+1);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	ll mxh = 0;
	for (ll i = 0; i < n; i++) {
		ll h, k;
		cin >> h >> k;
		sails_avail[h-1]++;
		mxh = max(mxh, h);
		if (h > k) sails_avail[h-k-1]--;
	}
	ll d = 0;
	ll cur = 0;
	for (ll i = mxh-1; i >= 0; i--) {
		d += sails_avail[i];
		cur += d;
		sails_above[i] = cur;
	}
	for (ll i = mxh-1; i >= 0; i--) {
		polls[i] = pil(mxh-i+1, sails_above[i]);
	}
	iota(sortable, sortable+mxh, 0);
	sort(sortable, sortable+mxh, comp);
	vector<pil> hull;
	hull.push_back(pil(0, 0));
	for (ll i = 0; i < mxh; i++) {
		pil cur = polls[sortable[i]];
		if (cur.first < hull.back().first) continue;
		while (hull.size() > 2 && contained(cur, hull[0], hull[hull.size()-2], hull[hull.size()-1])) hull.pop_back();
		hull.push_back(cur);
	}
	ll ans = 0;
	for (ll i = 1; i < hull.size(); i++)
		ans += ineff(hull[i].second-hull[i-1].second, hull[i].first-hull[i-1].first);
	cout << ans << "\n";
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:77:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for (ll i = 1; i < hull.size(); i++)
      |                 ~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 9 ms 4168 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1620 KB Output is correct
2 Incorrect 6 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2136 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2632 KB Output is correct

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5332 KB Output is correct
2 Incorrect 21 ms 3156 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

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