Submission #954826

#	Time	Username	Problem	Language	Result	Execution time	Memory
954826		sheldon	San (COCI17_san)	C++17	120 / 120	201 ms	33660 KiB

san

#include <bits/stdc++.h>

using namespace std;

vector<int> fenw;

void update (int idx) {
    while (idx < fenw.size()) {
        fenw[idx]++;
        idx = (idx | (idx + 1));
    }
}

int query (int idx) {
    int ans = 0;
    while (idx >= 0) {
        ans += fenw[idx];
        idx = (idx & (idx + 1)) - 1;
    }   
    return ans;
}

void solve() {
    int n;
    long long k;
    cin >> n >> k;
    vector<pair<int, int>> left, right;
    vector<int> vec;
    for (int i = 0; i < n / 2; ++i) {
        int x, y;
        cin >> x >> y;
        left.push_back({x, y});
        vec.push_back(x);
    }
    for (int i = n / 2; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        right.push_back({x, y});
        vec.push_back(x);
    }
    sort (vec.begin(), vec.end());
    vec.resize (unique (vec.begin(), vec.end()) - vec.begin());
    map<int, int> mp;
    int num = 0;
    for (int i = 0; i < vec.size(); ++i) {
        mp[vec[i]] = num++;
    }
    for (int i = 0; i < left.size(); ++i)  {
        left[i].first = mp[left[i].first];
    }
    for (auto &it : right) {
        it.first = mp[it.first];
    }
    long long ans = 0;
    vector<pair<long long, int>> coins;
    vector<vector<int>> locations (40);
    for (int mask = 1; mask < (1 << left.size()); ++mask) {
        int back = 0;

        long long have = 0;
        bool ok = 1;
        for (int bit = 0; bit < left.size() && ok; ++bit) {
            if (mask & (1 << bit)) {
                if (left[bit].first < back) {
                    ok = 0;
                    continue;
                }
                back = left[bit].first;
                have += left[bit].second;
            }
        }
        if (ok) {
            coins.push_back({have, back});
            if (have >= k) {
                ++ans;
            }
        }
    }
    sort (coins.begin(), coins.end());
    for (int i = 0; i < coins.size(); ++i) {
        locations[coins[i].second].push_back(i);
    }
    fenw.resize(coins.size ());
    vector<pair<int, long long>> heights;
    for (int mask = 1; mask < (1 << right.size()); ++mask) {
        bool ok = 1;
        int first = -1, back = 0;
        long long have = 0;
        for (int bit = 0; bit < right.size() && ok; ++bit) {
            if (mask & (1 << bit)) {
                if (first == -1) {
                    first = right[bit].first;
                }
                if (right[bit].first < back) {
                    ok = 0;
                }
                back = right[bit].first;
                have += right[bit].second;
            }   
        }
        if (ok) {
            heights.push_back({first, have});
            if (have >= k) {
                ++ans;
            }
        }
    }
    sort (heights.begin(), heights.end());
    int unlocked = 0, opened = 0;
    for (auto &it : heights) {
        int height = it.first;
        while (unlocked < 40 && unlocked <= height) {
            for (int x : locations[unlocked]) {
                update (x);
                ++opened;
            }
            ++unlocked;
        }

        long long need = k - it.second;
        int idx = lower_bound (coins.begin(), coins.end(), pair<long long, int>{need, (int) -1e9}) - coins.begin();
        ans += opened - query (idx - 1);
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

Compilation message (stderr)

san.cpp: In function 'void update(int)':
san.cpp:8:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     while (idx < fenw.size()) {
      |            ~~~~^~~~~~~~~~~~~
san.cpp: In function 'void solve()':
san.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 0; i < vec.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
san.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < left.size(); ++i)  {
      |                     ~~^~~~~~~~~~~~~
san.cpp:62:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for (int bit = 0; bit < left.size() && ok; ++bit) {
      |                           ~~~~^~~~~~~~~~~~~
san.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i = 0; i < coins.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~
san.cpp:89:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int bit = 0; bit < right.size() && ok; ++bit) {
      |                           ~~~~^~~~~~~~~~~~~~

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