Submission #771400

#TimeUsernameProblemLanguageResultExecution timeMemory
771400BidoTeimaSan (COCI17_san)C++17
0 / 120
113 ms13504 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; vector<pair<ll,int>>vals; const int N = (1 << 10) + 1; vector<vector<int>> st(4 * N); void build(int l, int r, int node){ st[node]=vector<int>(r-l+1); if(l == r){ st[node][0]=(vals[l].second); return; } int mid = (l + r) >> 1; build(l, mid, 2 * node + 1); build(mid + 1, r, 2 * node + 2); int i = 0, j = 0; while(i<(int)st[2 * node + 1].size() && j<(int)st[2 * node + 2].size()){ if(i == (int)st[2 * node + 1].size()){ st[node][i + j]=st[2 * node + 2][j]; ++j; continue; } if(j == (int)st[2 * node + 2].size()){ st[node][i + j]=st[2 * node + 1][i]; ++i; continue; } if(st[2 * node + 1][i] < st[2 * node + 2][j]){ st[node][i + j]=st[2 * node + 1][i]; ++i; }else{ st[node][i + j]=st[2 * node + 2][j]; ++j; } } } int query(int ql, int qr, int x, int l, int r, int node){ if(l>r)return 0; if(l > qr || r < ql)return 0; if(ql <= l && r <= qr){ return upper_bound(st[node].begin(), st[node].end(), x) - st[node].begin(); } int mid = (l + r) >> 1; return query(ql, qr, x, l, mid, 2 * node + 1) + query(ql, qr, x, mid + 1, r, 2 * node + 2); } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n; ll k; cin>>n>>k; int h[n],g[n]; for(int i = 0; i < n; i++){ cin>>h[i]>>g[i]; } if(n == 1){ return cout<<(g[0] >= k? 1 : 0), 0; } int n1 = n / 2, n2 = n - n1; ll ans = 0; for(int mask = 1; mask < (1 << n1); mask++){ vector<int>v; ll sum = 0; bool ok = 1; for(int i = 0; i < n1; i++){ if(mask & (1 << i)){ if(v.empty())v.push_back(i); else if(h[i] < h[v.back()]){ ok = 0; break; } else{ v.push_back(i); } sum += g[i]; } } if(!ok)continue; if(sum>=k)ans++; vals.push_back({sum, h[v.back()]}); } sort(vals.begin(), vals.end()); build(0, (int)vals.size() - 1, 0); for(int mask = 1; mask < (1 << n2); mask++){ vector<int>v; ll sum = 0; bool ok = 1; for(int i = 0; i < n2; i++){ if(mask & (1 << i)){ if(v.empty())v.push_back(i + n1); else if(h[i + n1] < h[v.back()]){ ok = 0; break; } else{ v.push_back(i + n1); } sum += g[i + n1]; } } if(!ok)continue; ans += query(lower_bound(vals.begin(), vals.end(), make_pair(k - sum, 0)) - vals.begin(), (int)vals.size() - 1, h[v.front()], 0, (int)vals.size() - 1, 0); if(sum>=k)ans++; } cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...