Submission #771353

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
771353	2023-07-02T22:42:55 Z	BidoTeima	San (COCI17_san)	C++17	Compilation error	0 ms	0 KB

san

#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

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){
      |                   ~~~~^