Submission #587437

#	Time	Username	Problem	Language	Result	Execution time	Memory
587437		GusterGoose27	Sails (IOI07_sails)	C++11	100 / 100	26 ms	4564 KiB

sails

#include <bits/stdc++.h>

using namespace std;

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

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

int n;

struct comp {
	bool operator()(const int &a, const int &b) {
		if (points[a].second*points[b].first == points[b].second*points[a].first) return points[a].first > points[b].first;
		return points[a].second*points[b].first < points[b].second*points[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, int x) {
	ll per = y/x;
	int 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;
	int mxh = 0;
	for (int i = 0; i < n; i++) {
		int 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 (int i = mxh-1; i >= 0; i--) {
		d += sails_avail[i];
		cur += d;
		sails_above[i] = cur;
	}
	for (int i = mxh-1; i >= 0; i--) {
		points[i] = pil(mxh-i, sails_above[i]);
	}
	iota(sortable, sortable+mxh, 0);
	sort(sortable, sortable+mxh, comp);
	vector<pil> hull;
	hull.push_back(pil(0, 0));
	for (int i = 0; i < mxh; i++) {
		pil cur = points[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 (int 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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10