Submission #1290267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290267		roger754	Sails (IOI07_sails)	C++20	0 / 100	1097 ms	8884 KiB

sails

#include <bits/stdc++.h>
#include "bits/stdc++.h"

#define int long long int
using namespace std;
#define F0R(i, n) for(int i = 0; i < n; i++)
#define MOD 1000000007
#define f first
#define s second

struct SegTree {
	const int sz;
	vector<int> nums;
	vector<int> tree;

	// Lazy tag exists for nodes on the border of propagation
	vector<int> lazy;


	// Apply lazy update onto node. Set lazy tag.
	void apply(int v, int len, int add) {
		tree[v] += len * add;
		lazy[v] += add;
	}


	void build(vector<int> &nums, int v, int sl, int sr) {
		if (sl == sr) {
			tree[v] = nums[sl];
			return;
		}
		int m = (sl + sr) / 2;
		build(nums, v * 2, sl, m);
		build(nums, v * 2 + 1, m + 1, sr);
		tree[v] = tree[v * 2] + tree[v * 2 + 1];
	}

	// Propagate lazy tag at v to its children. Set lazy tag to 0.
	// Propagation implies tree modification - those with lazy tags are
	// guaranteed to be modified.
	void push_down(int v, int l, int r) {
		int m = (l + r) / 2;
		apply(v * 2, m - l + 1, lazy[v]);
		apply(v * 2 + 1, r - m, lazy[v]);
		lazy[v] = 0;
	}

	void range_add(int v, int sl, int sr, int ql, int qr, int add) {
		if (sl > qr || sr < ql) return;
		if (ql <= sl && sr <= qr) {
			apply(v, sr - sl + 1, add);
			return;
		};
		push_down(v, sl, sr);
		int m = (sl + sr) / 2;
		range_add(v * 2, sl, m, ql, qr,add);
		range_add(v * 2 + 1, m + 1, sr, ql, qr, add);
		tree[v] = tree[v * 2] + tree[v * 2 + 1];
	}

	int range_query(int v, int sl, int sr, int ql, int qr) {
		if (sl > qr || sr < ql) return 0;
		if (ql <= sl && sr <= qr) { return tree[v]; };
		push_down(v, sl, sr);
		int m = (sl + sr) / 2;
		return range_query(v * 2, sl, m, ql, qr) + range_query(v * 2 + 1, m + 1, sr, ql, qr);
	}

	SegTree(vector<int> &nums) : sz(nums.size()), tree(sz * 4), nums(nums), lazy(sz * 4) {
		build(nums, 1, 0, sz - 1);
	}

	SegTree(int len) : sz(len), tree(sz * 4), nums(len), lazy(sz * 4) {
		build(nums, 1, 0, sz - 1);
	}


	int query(int l, int r) {
		return range_query(1, 0, sz - 1, l, r);
	}

	void add(int l, int r, int add) {
		range_add(1, 0, sz - 1, l, r, add);
	}

};





signed main() {
	int n;
	cin >> n;

	vector<pair<int,int>> masts(n);
	F0R(i, n) {
		int h, k;
		cin >> h >> k;
		masts[i].f = h;
		masts[i].s = k;
	}

	sort(masts.begin(), masts.end());
	int max_height = masts[n-1].first;
	SegTree sails(max_height);

	int ans = 0;
	F0R(i,n) {
		int u = masts[i].f;

		int sails_placed = 0;
		while (sails_placed < masts[i].s) {
			int lo = 0;
			int hi = (u-1);
			int target = sails.query(u-1, u-1);

			while (hi>lo) {
				int mid = lo + (hi-lo)/2;
				if (sails.query(mid, mid) > target) {
					lo = mid+1;
				} else {
					hi = mid;
				}
			}

			int amt = min(u-lo,  (masts[i].s-sails_placed));

			sails.add(lo, lo+amt-1, 1);

			/*
			cout << "(" << masts[i].f << " " << masts[i].s << ") ";
			for (int i = 0; i < n; i++ ) {
				cout << sails.query(i,i) << " ";
			}
			cout << '\n';
			*/

			sails_placed += amt;
			ans += amt * (target);
			u = lo-1;
		}
	}


	cout << ans;
}

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