Submission #771353

#TimeUsernameProblemLanguageResultExecution timeMemory
771353BidoTeimaSan (COCI17_san)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; vector<pair<ll,int>>vals; const int N = 1 << 20; vector<int> st[4 * N]; void build(int l, int r, int node){ if(l == r){ st[node].push_back(vals[l].second); return; } int mid = (l + r) >> 1; build(l, mid, 2 * node + 1); build(mid + 1, r, 2 * node + 2); int l = 0, r = 0; while((int)st[node].size()<r-l+1){ if(l == (int)st[2 * node + 1].size()){ st[node].push_back(st[2 * node + 2][r]); ++r; continue; } if(r == (int)st[2 * node + 2].size()){ st[node].push_back(st[2 * node + 1][r]); ++l; continue; } if(st[2 * node + 1][l] < st[2 * node + 2][r]){ st[node].push_back(st[2 * node + 1][l]); ++l; }else{ st[node].push_back(st[2 * node + 2][r]); ++r; } } } int query(int ql, int qr, int x, int l, int r, int node){ 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; 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; vals.push_back({sum, h[v.back()]}); } assert(vals.size()); sort(vals.begin(), vals.end()); build(0, (int)vals.size() - 1, 0); ll ans = 0; for(int mask = 0; 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); else if(h[i + n1] < h[v.back()]){ ok = 0; break; } else{ v.push_back(i + n1); } sum += g[i + n1]; } } if(!ok)continue; if(mask == 0){ ans += vals.end() - lower_bound(vals.begin(), vals.end(), make_pair(k, 0)); }else{ ans += query(lower_bound(vals.begin(), vals.end(), make_pair(k - sum, 0)) - vals.begin(), (int)vals.size() - 1, v.front(), 0, (int)vals.size() - 1, 0); } } cout<<ans; return 0; }

Compilation message (stderr)

san.cpp: In function 'void build(int, int, int)':
san.cpp:15:9: error: declaration of 'int l' shadows a parameter
   15 |     int l = 0, r = 0;
      |         ^
san.cpp:7:16: note: 'int l' previously declared here
    7 | void build(int l, int r, int node){
      |            ~~~~^
san.cpp:15:16: error: declaration of 'int r' shadows a parameter
   15 |     int l = 0, r = 0;
      |                ^
san.cpp:7:23: note: 'int r' previously declared here
    7 | void build(int l, int r, int node){
      |                   ~~~~^