#include<bits/stdc++.h>
using namespace std;
const int MAX = 2500005;
int n, h[2][25], g[2][25], m[2], K;
long long cnt, ans;
vector<int> vec[2];
map<int,vector<long long> > mp[2];
map<long long, long long> lab;
set<long long> gold;
struct BIT {
int v[MAX];
void update(int _pos) {
for (; _pos < MAX; _pos += _pos&-_pos) v[_pos]++;
}
int get(int _pos) {
int res = 0;
for (; _pos; _pos -= _pos&-_pos) res += v[_pos];
return res;
}
} bit;
void sieve(int id) {
for (int mask = 1; mask < (1 << m[id]); ++mask) {
vector<int> x;
int c = 0;
for (int i = 0; i < m[id]; ++i) {
if ( (mask >> i) & 1 ) x.push_back(h[id][i]), c += g[id][i];
}
bool ok = 1;
for (int i = 0; i < x.size() - 1; ++i) {
if (x[i] > x[i + 1]) { ok = 0; break; }
}
if (!ok) continue;
int _h = (id ? x[0] : x.back() );
vec[id].push_back(_h);
mp[id][_h].push_back(c);
if (c >= K) ans++;
gold.insert(c);
}
sort(vec[id].begin(), vec[id].end() );
vec[id].erase (unique (vec[id].begin(), vec[id].end()), vec[id].end() );
}
void upd (int pter) {
for (auto go : mp[1][pter]) {
bit.update(lab[go]);
}
}
void ge (int _gold) {
set<int>::iterator it = gold.lower_bound (K - _gold);
ans += bit.get (cnt) - bit.get (lab[*it] - 1);
}
signed main () {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> K;
m[0] = n / 2; m[1] = n- m[0];
for (int i = 0; i < n; ++i) {
int _h, _g; cin >> _h >> _g;
if (i < m[0]) {
h[0][i] = _h; g[0][i] = _g;
}
else {
h[1][i - m[0] ] = _h; g[1][i - m[0] ] = _g;
}
}
sieve(0); sieve(1);
for (int go : gold) {
lab[go] = ++cnt;
}
int pter = vec[1].size() - 1;
for (int i = vec[0].size() - 1; i >= 0; --i) {
while (pter >= 0 && vec[1][pter] >= vec[0][i]) {
upd (vec[1][pter]);
pter--;
}
for (int j = 0; j < mp[0][ vec[0][i] ].size(); ++j) {
ge (mp[0][ vec[0][i] ][j]);
}
}
cout << ans;
return 0;
}
Compilation message
san.cpp: In function 'void sieve(int)':
san.cpp:32:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < x.size() - 1; ++i) {
~~^~~~~~~~~~~~~~
san.cpp: In function 'void ge(int)':
san.cpp:53:46: error: conversion from 'std::set<long long int>::iterator {aka std::_Rb_tree_const_iterator<long long int>}' to non-scalar type 'std::set<int>::iterator {aka std::_Rb_tree_const_iterator<int>}' requested
set<int>::iterator it = gold.lower_bound (K - _gold);
~~~~~~~~~~~~~~~~~^~~~~~~~~~~
san.cpp: In function 'int main()':
san.cpp:83:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < mp[0][ vec[0][i] ].size(); ++j) {
~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
