Submission #237924

#	Time	Username	Problem	Language	Result	Execution time	Memory
237924		MrRobot_28	San (COCI17_san)	C++17	120 / 120	358 ms	41504 KiB

san

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

#define int long long
vector <int> tree;
void update(int v, int l, int r, int ind)
{
	tree[v]++;
	if(l == r)
	{
		return;
	}
	if(ind <= (r + l) / 2)
	{
		update(v * 2, l, (r + l) / 2, ind);
	}
	else
	{
		update(v * 2 + 1, (r + l) / 2 + 1, r, ind);
	}
}
int ans(int v, int l, int r, int al, int ar)
{
	if(l >= al && r <= ar)
	{
		return tree[v];
	}
	else if(l <= ar && r >= al)
	{
		return ans(v * 2, l, (r + l) / 2, al, ar) + ans(v * 2 + 1, (r + l) /2  + 1, r, al, ar);
	}
	else
	{
		return 0;
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	vector <int> h(n), g(n);
	for(int i = 0; i < n; i++)
	{
		cin >> h[i] >> g[i];
	}
	int len1 = n / 2;
	vector <int> uniq;
	int len2 = n - n / 2;
	vector <pair <int, int> > vec, vec1;
	for(int i = 0; i < (1 << len2); i++)
	{
		int lasth = 0;
		int sum = 0;
		int h1 = 0;
		bool flag = true;
		for(int j = 0; j < len2; j++)
		{
			if((1 << j) & i)
			{
				if(lasth == 0)
				{
					h1 = h[j + len1];
				}
				if(lasth > h[j + len1])
				{
					flag = false;
				}
				lasth = h[j + len1];
				sum += g[j + len1];
			}
		}
		if(sum == 0){
			h1 = 1e9;
		}
		if(flag)
		{
			uniq.push_back(sum);
			vec.push_back({h1, sum});
		}
	}
	sort(uniq.begin(), uniq.end());
	int sz = unique(uniq.begin(), uniq.end()) - uniq.begin();
	tree.resize(4 * sz);
	for(int i = 0; i < (1 << len1); i++)
	{
		int lasth = 0, sum = 0;
		bool flag = true;
		for(int j = 0; j < len1; j++)
		{
			if((1 << j) & i)
			{
				if(lasth > h[j])
				{
					flag = false;
				}
				lasth = h[j];
				sum += g[j];
			}
		}
		if(flag)
		{
			vec1.push_back({lasth, sum});
		}
	}
	sort(vec.begin(), vec.end());
	sort(vec1.begin(), vec1.end());
	multiset <int> p;
	int j = vec.size() - 1;
	int sum = 0;
	for(int i = vec1.size() - 1; i >= 0; i--)
	{
		while(j >= 0 && vec[j].first >= vec1[i].first)
		{
			int ind = lower_bound(uniq.begin(), uniq.begin() + sz, vec[j].second) - uniq.begin();
			update(1, 0, sz - 1, ind);
			j--;
		}
		int ind = lower_bound(uniq.begin(), uniq.begin() + sz, k - vec1[i].second) - uniq.begin();
		if(ind != sz)
		{
			sum += ans(1, 0, sz - 1, ind, sz - 1);
		}
	}
	cout << sum;
	return 0;
}

• Subtask 1: 24 / 24
• Subtask 2: 24 / 24
• Subtask 3: 24 / 24
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24