Submission #886728

#	Time	Username	Problem	Language	Result	Execution time	Memory
886728		noyancanturk	San (COCI17_san)	C++17	48 / 120	434 ms	65536 KiB

san

#ifndef Local
    #pragma GCC optimize("O3,unroll-loops")
    const int lim=1000;
#else
    const int lim=1000;
#endif

#include "bits/stdc++.h"
using namespace std;

#define int int64_t
#define pb push_back

const int mod=1e9+7;
using pii=pair<signed,signed>;

struct fenwick{
    int n;
    int tree[lim];
    fenwick(int n):n(n){
        memset(tree,0,sizeof(tree));
    }
    void update(int p,int val){
        p++;
        while(p<=n){
            tree[p]+=val;
            p+=p&-p;
        }
    }
    int query(int p){
        p++;
        int res=0;
        while(0<p){
            res+=tree[p];
            p-=p&-p;
        }
        return res;
    }
    int query(int l,int r){
        return query(r)-query(l-1);
    }
};

inline void solve(){
    int n,k;
    cin>>n>>k;
    pii a[n];
    int lens[n];
    for(int i=0;i<n;i++){
        cin>>a[i].first>>a[i].second;
        lens[i]=a[i].first;
    }
    if(n<=20){
        int ans=0;
        for(int m=1;m<(1<<n);m++){
            int past=-1,cur=0;
            for(int i=0;i<n;i++){
                if(!(m&(1<<i)))continue;
                if(!(~past)||a[past].first<=a[i].first){
                    cur+=a[i].second;
                    past=i;
                }else{
                    goto nextt;
                }
            }
            if(k<=cur){
                //cerr<<"passed "<<(bitset<4>(m))<<" "<<cur<<"\n";
                ans++;
                continue;
            }
            nextt:;
            //cerr<<"failed "<<(bitset<4>(m))<<"\n";
        }
        cout<<ans<<"\n";
    }else{
        sort(lens,lens+n);
        unordered_map<int,int>to;
        for(int i=0;i<n;i++){
            to[lens[i]]=i;
        }
        for(int i=0;i<n;i++){
            a[i].first=to[a[i].first];
        }
        map<signed,vector<signed>>begins,ends;
        for(int m=1;m<(1<<20);m++){
            int past=-1,cur=0;
            for(int i=0;i<20;i++){
                if(!(m&(1<<i)))continue;
                if(!(~past)||a[past].first<=a[i].first){
                    cur+=a[i].second;
                    past=i;
                }else{
                    goto nexttt;
                }
            }
            begins[cur].pb(a[past].first);
            nexttt:;
        }
        for(int m=1;m<(1<<(n-20));m++){
            int first=-1,past=-1,cur=0;
            for(int i=0;i<(n-20);i++){
                if(!(m&(1<<i)))continue;
                if(!(~past)){
                    first=i+20;
                }
                if(!(~past)||a[past].first<=a[i+20].first){
                    cur+=a[i+20].second;
                    past=i+20;
                }else{
                    goto nextttt;
                }
            }
            ends[cur].pb(a[first].first);
            nextttt:;
        }
        fenwick all(500);
        int ans=0;
        auto j=ends.rbegin();
        for(auto [p,c]:begins){
            while(j!=ends.rend()&&k<=j->first+p){
                //cerr<<"updated"<<j->first.second<<" "<<j->second<<"\n";
                for(int jj:j->second){
                    all.update(jj,1);
                }
                j++;
            }
            //cerr<<p.first<<" "<<p.second<<" "<<all.query(p.second-1,50)<<"\n";
            for(int jj:c){
                ans+=all.query(jj,100);
            }
        }
        //cerr<<all.query(0,50)<<"\n";
        cout<<ans<<"\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
#ifdef Local  
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#else
    //freopen("grass.in","r",stdin);
    //freopen("grass.out","w",stdout);
#endif
    int t=1;
    //cin>>t;
    while (t--)
    {
        solve();
    }
}

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