Submission #108168

#	Time	Username	Problem	Language	Result	Execution time	Memory
108168		FiloSanza	San (COCI17_san)	C++14	0 / 120	173 ms	66560 KiB

san

#include <bits/stdc++.h>

using namespace std;

//#define int long long

struct comparer{
    bool operator()(const pair<int, int>& a, const int& b){
        return a.first < b;
    }
    bool operator()(const int& a, const pair<int, int>& b){
        return a < b.first;
    }
};

int n, N, K;
vector<int> v;
vector<int> h;

//O(2^N/2)
void jump(int last, int start, int i, int coins, vector<pair<int, int>>& sum){
    if(i == n && start == -1) return;
    if(i == n) return sum.push_back({coins, i == N ? start : last});
    if(start == -1 || last <= h[i]) jump(h[i], start == -1 ? h[i] : start, i+1, coins + v[i], sum);
    jump(last, start, i+1, coins, sum);
}

//O(log(2^N/2) + N)
long long cont(const pair<int, int>& value, const vector<pair<int, int>>& right, const vector<vector<int>>& contH){
    long long ans = 0;
    int diff = K-value.first;
    auto it = lower_bound(right.begin(), right.end(), diff, comparer());
    if(it == right.end()) return 0;
    int idx = it - right.begin();
    for(int i=value.second; i<contH[idx].size(); i++) ans += 1LL*contH[idx][i];
    return ans;
}

signed main(){
    cin.tie(0);
    cin.sync_with_stdio(0);

    cin >> N >> K;
    v.resize(N);
    h.resize(N);

    for(int i=0; i<N; i++)
        cin >> h[i] >> v[i];

    int sub = 0;
    map<int, int> remap;
    for(auto i : h) remap[i]++;
    for(auto &i : remap) i.second = sub++;
    for(auto &i : h) i = remap[i];

    vector<pair<int, int>> left, right;
    left.reserve(1<<(N/2));
    right.reserve(1<<(N/2));
    n = N/2;
    jump(-1, -1, 0, 0, left);
    n = N;
    jump(-1, -1, N/2, 0, right);

    sort(left.begin(), left.end());
    sort(right.begin(), right.end());

    vector<int> tmp(sub, 0);
    vector<vector<int>> contH(right.size());
    for(int i=right.size()-1; i>=0; i--){
        tmp[right[i].second]++;
        contH[i] = tmp;
    }
    
    long long ans = 0;
    for(auto i : left) if(i.first >= K) ans++;
    for(auto i : right) if(i.first >= K) ans++;
    for(auto i : left) ans += cont(i, right, contH);

    cout << ans;
/*
    cout << "\n\nDEBUG\n";
    for(auto i : left) cout << i.first << " " << i.second << " "; cout << "\n";
    for(auto i : right) cout << i.first << " " << i.second << " "; cout << "\n";
*/
}

Compilation message (stderr)

san.cpp: In function 'long long int cont(const std::pair<int, int>&, const std::vector<std::pair<int, int> >&, const std::vector<std::vector<int> >&)':
san.cpp:35:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=value.second; i<contH[idx].size(); i++) ans += 1LL*contH[idx][i];
                             ~^~~~~~~~~~~~~~~~~~

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