Submission #771367

#	Time	Username	Problem	Language	Result	Execution time	Memory
771367		BidoTeima	San (COCI17_san)	C++17	0 / 120	32 ms	65536 KiB

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 i = 0, j = 0;
    while((int)st[node].size()<r-l+1){
        if(i == (int)st[2 * node + 1].size()){
            st[node].push_back(st[2 * node + 2][j]);
            ++j;
            continue;
        }
        if(j == (int)st[2 * node + 2].size()){
            st[node].push_back(st[2 * node + 1][i]);
            ++i;
            continue;
        }
        if(st[2 * node + 1][i] < st[2 * node + 2][j]){
            st[node].push_back(st[2 * node + 1][i]);
            ++i;
        }else{
            st[node].push_back(st[2 * node + 2][j]);
            ++j;
        }
    }
}
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(__builtin_popcount(mask) == 1)while(true); 
        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);
        }
        if(sum>=k)ans++;
    }
    cout<<ans;
    return 0;
}

• Subtask 1: 0 / 24
• Subtask 2: 0 / 24
• Subtask 3: 0 / 24
• Subtask 4: 0 / 24
• Subtask 5: 0 / 24