Submission #1046349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046349		hiuwsss	Sails (IOI07_sails)	C++14	100 / 100	45 ms	2652 KiB

sails

/*
Ý tưởng giống bài BOI11_grow trong OJUZ
ta k cần quan tâm đến việc nó nằm ở cột nào, mà chỉ cần quan tâm đến các tầng, tầng x có Sx buồm thì của giá trị của nó sẽ Sx * (Sx - 1) /2;
Ta có bài toán tham lam sau : sắp xếp các cột theo độ cao tăng dần, để cho tổng nhỏ nhất thì các giá trị càng gần nhau và càng nhỏ càng tốt, từ đó ta có thể tham lam
Xét tới cột i, có độ cao h, có c lá buồm thì ta sẽ chọn ra c tầng nhỏ nhất để cho vào.

Ta muốn xây dựng 1 cây BIT tăng dàn, vì ở độ cao càng bé thì sẽ càng có nhiều cột thỏa mãn, nên việc tham lam sẽ luôn có cột càng nhỏ nên ta cài đặt như ở dưới. 
*/

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> i) & 1LL)
#define ll long long

template<class T> bool minimize(T &x, const T &y) {
	return x > y ? x = y, 1 : 0;
}

template<class T> bool maximize(T &x, const T &y) {
	return x < y ? x = y, 1 : 0;
}

const int MAX = 1e5 + 5;
const int max_log = 18;

int n;
pair<int, int> a[MAX];

struct FenwickTree {
	int n;
	vector<int> bit;

	FenwickTree(int _n = 0) {
		n = _n;
		bit.assign(n + 5, 0);
	}

	void update(int u, int delta) {
		for (; u <= n; u += (u & (-u))) bit[u] += delta;
	}

	void update(int l, int r, int delta) {
		if (l > r) return;
		update(l, delta); update(r + 1, -delta);
	}

	int getValue(int u) {
		int ans = 0;
		for (; u > 0; u -= (u & (-u))) ans += bit[u];
		return ans;
	}

	int getPos(int value) {
		int pos = 0, sum = 0;
		FORD(i, max_log, 0)
			if (pos + MASK(i) <= n && sum + bit[pos + MASK(i)] <= value) {
				pos |= MASK(i);
				sum += bit[pos];
			}

		return pos;
	}
};

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

	#define TASK ""
	if (fopen(TASK".inp", "r")) {
		freopen(TASK".inp", "r", stdin);
		freopen(TASK".out", "w", stdout);
	}

	cin >> n;

	int maxHeight = 0;
	FOR(i, 1, n) {
		cin >> a[i].first >> a[i].second;
		maximize(maxHeight, a[i].first);
	}

	sort(a + 1, a + n + 1);

	FenwickTree myBit(maxHeight);
	FOR(i, 1, n) {
		int h = a[i].first, c = a[i].second;

		int L = maxHeight - h + 1;
		int value = myBit.getValue(L + c - 1);
		int R = myBit.getPos(value);
		int r = max(L - 1, myBit.getPos(value - 1));

		myBit.update(L, r, 1);
		myBit.update(R - (c - (r - L + 1)) + 1, R, 1);
	}

	ll res = 0;
	FOR(i, 1, maxHeight) {
		int cur = myBit.getValue(i);
		res += 1LL * cur * (cur - 1) / 2;
	}

	cout << res;

	return (0 ^ 0);
}

//hiuwsss

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:76:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   freopen(TASK".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sails.cpp:77:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   freopen(TASK".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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