#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void io();
int N;
ll K;
int H[42];
ll G[42];
v<int> adjL[42], v<int> adjR[42];
v<ll> goldL[42], goldR[42];
void compress() {
map<ll, int> conv;
FORE(i, 0, N + 1)
conv[H[i]] = 0;
int num = 0;
for (auto en : conv)
conv[en.first] = num++;
FORE(i, 0, N + 1)
H[i] = conv[H[i]];
}
void makeAdj() {
assert(N >= 21);
FORE(i, 0, 20) FORE(j, i + 1, 20)
if (H[i] <= H[j])
adjL[i].push_back(j);
FORE(i, 21, N + 1) FOR(j, 21, i - 1)
if (H[j] <= H[i])
adjR[i].push_back(j);
}
void dfs(int i, int g, v<ll> gold[], v<int> adj[]) {
g += G[i];
gold[H[i]].push_back(g);
for (int j : adj[i])
dfs(j, g, gold, adj);
}
ll query(int lh, ll lg) { // left Hight, left Gold
ll ans = 0;
FOR(rh, lh, 42) {
auto it = lower_bound(goldR[rh].begin(), goldR[rh].end(), K - lg);
ans += (int)(it - goldR[rh].begin());
}
return ans;
}
int solve() {
compress();
makeAdj();
dfs(0, 0, goldL, adjL);
dfs(N + 1, 0, goldR, adjR);
FOR(h, 0, 42) {
vsort(goldL[h]);
vsort(goldR[h]);
}
ll ans = 0;
FOR(lh, 0, 42)
for (int gold : goldL[lh])
ans += query(lh, gold);
return ans;
}
ll naive() {
map<ll, ll> cnt[42];
v<int> adj[42];
cnt[N + 1][0] = 1;
RFORE(i, N, 0)
FOR(j, i + 1, N + 2)
if (H[i] <= H[j])
for (auto entry : cnt[j])
cnt[i][min(K, entry.first + G[i])] += entry.second;
return cnt[0][K];
}
int main() {
io();
cin >> N >> K;
FORE(i, 1, N)
cin >> H[i] >> G[i];
H[N + 1] = 1e9 + 1;
if (N < 21) cout << naive() << "\n";
else cout << solve() << "\n";
return 0;
}
void io() {
#ifdef LOCAL_PROJECT
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#else
// add i/o method of specific testing system
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
Compilation message
san.cpp:29:25: error: invalid declarator before 'adjR'
v<int> adjL[42], v<int> adjR[42];
^~~~
san.cpp: In function 'void makeAdj()':
san.cpp:50:4: error: 'adjR' was not declared in this scope
adjR[i].push_back(j);
^~~~
san.cpp:50:4: note: suggested alternative: 'adjL'
adjR[i].push_back(j);
^~~~
adjL
san.cpp: In function 'int solve()':
san.cpp:73:23: error: 'adjR' was not declared in this scope
dfs(N + 1, 0, goldR, adjR);
^~~~
san.cpp:73:23: note: suggested alternative: 'adjL'
dfs(N + 1, 0, goldR, adjR);
^~~~
adjL