oj.uz

Submission #954826

# Submission time Handle Problem Language Result Execution time Memory
954826 2024-03-28T16:25:44 Z sheldon San (COCI17_san) C++17
120 / 120
 201 ms 33660 KB 
#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

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.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2452 KB Output is correct
2 Correct 3 ms 604 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7512 KB Output is correct
2 Correct 17 ms 1240 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 33660 KB Output is correct
2 Correct 99 ms 4544 KB Output is correct