oj.uz

Submission #237924

# Submission time Handle Problem Language Result Execution time Memory
237924 2020-06-09T10:37:12 Z MrRobot_28 San (COCI17_san) C++17
120 / 120
 358 ms 41504 KB 
#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.0 / 24.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4976 KB Output is correct
2 Correct 14 ms 640 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 9432 KB Output is correct
2 Correct 61 ms 1652 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 41504 KB Output is correct
2 Correct 163 ms 4452 KB Output is correct