Submission #588939

#	Time	Username	Problem	Language	Result	Execution time	Memory
588939		Drew_	Hiring (IOI09_hiring)	C++17	60 / 100	358 ms	31224 KiB

hiring

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

#define pb push_back
#define f1 first
#define s2 second
// #define int long long

using ll = long long;
using ii = pair<int, int>;
using pl = pair<ll, ll>;

const int MAX = 5e5 + 69;

struct Segtree
{
	int n;
	pair<ll, int> st[1 << 20];
	Segtree() {}
	Segtree(int n_) : n(n_) { memset(st, 0, sizeof(st)); }

	inline void add(int p, ll val)
	{
		const auto add_ = [&](const auto &self, int node, int l, int r) -> void
		{
			if (l > p || r < p)
				return;
			if (p <= l && r <= p)
			{
				st[node].f1 += val; st[node].s2++;
				return;
			}
			int mid = (l + r) >> 1;
			self(self, node << 1, l, mid);
			self(self, node << 1 | 1, mid+1, r);

			st[node].f1 = st[node << 1].f1 + st[node << 1 | 1].f1;
			st[node].s2 = st[node << 1].s2 + st[node << 1 | 1].s2;
		};
		add_(add_, 1, 1, n);
	}

	inline int query(ll val, ll S)
	{
		int res = 0;
		const auto query_ = [&](const auto &self, int node, int l, int r) -> void
		{
			if (st[node].f1 * S <= val)
			{
				res += st[node].s2;
				val -= st[node].f1 * S;
				return;
			}

			if (l == r)
				return;
			
			int mid = (l + r) >> 1;
			if (st[node << 1].f1 * S <= val)
			{
				res += st[node << 1].s2;
				val -= st[node << 1].f1 * S;
				self(self, node << 1 | 1, mid+1, r);
			}
			else self(self, node << 1, l, mid);
		};
		query_(query_, 1, 1, n);
		return res;
	}
};

int32_t main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N;
	ll W;
	cin >> N >> W;

	vector<array<int, 4>> V(N);
	for (auto &[s, q, i, idx] : V)
		cin >> s >> q;
	for (int i = 0; i < N; ++i)
		V[i][3] = i+1;

	sort(V.begin(), V.end(), [](auto &x, auto &y){
		return x[1] < y[1];
	});

	for (int i = 0; i < N; ++i)
		V[i][2] = i+1;

	sort(V.begin(), V.end(), [](auto &x, auto &y){
		return 1ll * x[0] * y[1] < 1ll * y[0] * x[1];
	});

	Segtree st(N);

	int res = 0, id = -1;
	for (int j = 0; j < N; ++j)
	{
		auto &[s, q, i, idx] = V[j];

		st.add(i, q);
		int cur = st.query(1ll * W * q, s);
		if (cur > res)
			res = cur, id = j;
	}

	sort(V.begin(), V.begin()+id+1, [](auto &x, auto &y){
		return x[1] < y[1];
	});

	cout << res << '\n';
	for (int i = 0; i < res; ++i)
		cout << V[i][3] << '\n';
	return 0;
}

Compilation message (stderr)

hiring.cpp: In constructor 'Segtree::Segtree(int)':
hiring.cpp:20:52: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   20 |  Segtree(int n_) : n(n_) { memset(st, 0, sizeof(st)); }
      |                                                    ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from hiring.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, int>' declared here
  211 |     struct pair
      |            ^~~~

• Subtask 1: 19 / 30
• Subtask 2: 20 / 28
• Subtask 3: 3 / 6
• Subtask 4: 3 / 6
• Subtask 5: 3 / 6
• Subtask 6: 3 / 6
• Subtask 7: 3 / 6
• Subtask 8: 3 / 6
• Subtask 9: 3 / 6