oj.uz

Submission #587437

# Submission time Handle Problem Language Result Execution time Memory
587437 2022-07-01T21:17:10 Z GusterGoose27 Sails (IOI07_sails) C++11
100 / 100
 26 ms 4564 KB 
#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

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.0 / 5.0

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

Subtask #2
10.0 / 10.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 #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 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 8 ms 3412 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1880 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3788 KB Output is correct
2 Correct 23 ms 4328 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4564 KB Output is correct
2 Correct 15 ms 2788 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4096 KB Output is correct
2 Correct 18 ms 2244 KB Output is correct