oj.uz

Submission #201662

# Submission time Handle Problem Language Result Execution time Memory
201662 2020-02-11T16:20:14 Z Saboon San (COCI17_san) C++14
120 / 120
 378 ms 28344 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 300000 + 10;
const int maxN = (1 << 21) + 10;

int fen[maxN];

int get(int x){
	int ret = 0;
	for (x = max(0, x + 1); x; x -= x & -x)
		ret += fen[x];
	return ret;
}

void add(int x){
	for (x ++; x < maxN; x += x & -x)
		fen[x] ++;
}

vector<pair<ll,ll> > get(vector<pair<ll,ll> > &a, bool wh){
	vector<pair<ll,ll>> c;
	int n = a.size();
	for (int mask = 1; mask < (1 << n); mask++){
		ll last = -1, first = -1;
		bool flag = 1;
		ll sum = 0;
		for (int i = 0; i < n; i++){
			if (!(mask & (1 << i)))
				continue;
			if (last > a[i].first){
				flag = 0;
				break;
			}
			if (first == -1)
				first = a[i].first;
			last = a[i].first;
			sum += a[i].second;
		}
		if (flag == 0)
			continue;
		if (wh == 0)
			c.push_back({last, sum});
		else
			c.push_back({first, sum});
	}
	if (wh == 0)
		c.push_back({1, 0});
	else
		c.push_back({1000*1000*1000, 0});
	return c;
}

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	ll k;
	cin >> n >> k;
	vector<pair<ll,ll> > a, b;
	for (int i = 0; i < n; i++){
		ll h, g;
		cin >> h >> g;
		if (i < n / 2)
			a.push_back({h, g});
		else
			b.push_back({h, g});
	}
	vector<pair<ll,ll>> c = get(a, 0);
	vector<pair<ll,ll>> d = get(b, 1);
	sort(c.begin(), c.end());
	sort(d.begin(), d.end());
	vector<ll> cmp;
	for (auto it : c)
		cmp.push_back(it.second);
	for (auto it : d)
		cmp.push_back(k - it.second - 1);
	sort(cmp.begin(), cmp.end());
	cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
	for (auto& it : c)
		it.second = lower_bound(cmp.begin(), cmp.end(), it.second) - cmp.begin() + 1;
	for (auto& it : d)
		it.second = lower_bound(cmp.begin(), cmp.end(), k - it.second - 1) - cmp.begin() + 1;
	int ptr = 0;
	n = c.size();
	int m = d.size();
	ll answer = 0;

	for (int i = 0; i < d.size(); i++){
		while (ptr < n and c[ptr].first <= d[i].first){
			add(c[ptr ++].second);
		}
		answer += ptr - get(d[i].second);
	}
	cout << answer << endl;
}

Compilation message

san.cpp: In function 'int main()':
san.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < d.size(); i++){
                  ~~^~~~~~~~~~
san.cpp:86:6: warning: unused variable 'm' [-Wunused-variable]
  int m = d.size();
      ^

Subtask #1
24.0 / 24.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3432 KB Output is correct
2 Correct 8 ms 632 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 6876 KB Output is correct
2 Correct 27 ms 1400 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 28344 KB Output is correct
2 Correct 138 ms 6632 KB Output is correct