Submission #381510

#TimeUsernameProblemLanguageResultExecution timeMemory
381510AdiZer0San (COCI17_san)C++17
120 / 120
413 ms63656 KiB
#include <bits/stdc++.h> #define pb push_back #define whole(x) x.begin(), x.end() #define sz(x) (int)x.size() using namespace std; typedef long long ll; typedef long double ld; const int N = (int)1e6 + 7; const int INF = (int)1e9 + 7; const ll linf = (ll)1e18 + 1; int h[43], g[43]; ll t[N * 4]; vector<ll> mark[N]; vector<pair<int, ll>> ord; void update(int v, int tl, int tr, int pos, int val) { if (tl == tr) t[v] += val; else { int tm = tl + tr >> 1; if (pos <= tm) update((v << 1), tl, tm, pos, val); else update((v << 1) + 1, tm + 1, tr, pos, val); t[v] = t[(v << 1)] + t[(v << 1) + 1]; } } ll get(int v, int tl, int tr, int l, int r) { if (tl > r || tr < l || l > r) return 0; if (l <= tl && tr <= r) return t[v]; int tm = tl + tr >> 1; return get((v << 1), tl, tm, l, r) + get((v << 1) + 1, tm + 1, tr, l, r); } int main() { ll k; int n; scanf ("%d %lld", &n, &k); for (int i = 0; i < n; ++i) scanf ("%d %d", h + i, g + i); int half = n / 2; ll ways = 0; vector<pair<int, ll>> all; for (int i = 1; i < (1 << half); ++i) { bool bad = false; int p = -1; ll gold = 0; for (int j = 0; j < half; ++j) { if ((i >> j) & 1) { if (p == -1) gold += g[j], p = j; else if (h[p] <= h[j]) gold += g[j], p = j; else bad = true; } } if (bad) continue; if (gold >= k) ++ways; all.pb({h[p], gold}); } int rem = n - half; for (int i = 1; i < (1 << rem); ++i) { bool bad = false; int st = -1, p = -1; ll gold = 0; for (int j = 0; j < rem; ++j) { if ((i >> j) & 1) { if (p == -1) st = j + half, p = j + half, gold += g[j + half]; else if (h[p] <= h[j + half]) p = j + half, gold += g[j + half]; else bad = true; } } if (bad) continue; if (gold >= k) ++ways; ord.pb({h[st], gold}); } sort(whole(ord)); vector<int> pos; for (int i = 0; i < sz(ord); ++i) pos.pb(ord[i].first); vector<ll> comp; for (int i = 0; i < sz(ord); ++i) comp.pb(ord[i].second); for (auto to : all) { int last = to.first; int l = (lower_bound(whole(pos), last) - pos.begin()); ll rem = max(0 * 1ll, k - to.second); comp.pb(rem); mark[l].push_back(rem); } sort(whole(comp)); comp.resize(unique(whole(comp)) - comp.begin()); for (int i = sz(ord) - 1; i >= 0; --i) { ord[i].second = (lower_bound(whole(comp), ord[i].second) - comp.begin()) + 1; update(1, 1, sz(ord) + sz(all), ord[i].second, 1); if (!mark[i].empty()) { for (ll to : mark[i]) { if (to > comp[sz(comp) - 1]) continue; int cur_pos = (lower_bound(whole(comp), to) - comp.begin()) + 1; ways += get(1, 1, sz(ord) + sz(all), cur_pos, sz(ord) + sz(all)); } } } printf ("%lld\n", ways); return 0; }

Compilation message (stderr)

san.cpp: In function 'void update(int, int, int, int, int)':
san.cpp:24:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |         int tm = tl + tr >> 1;
      |                  ~~~^~~~
san.cpp: In function 'll get(int, int, int, int, int)':
san.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
san.cpp: In function 'int main()':
san.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |     int n; scanf ("%d %lld", &n, &k);
      |            ~~~~~~^~~~~~~~~~~~~~~~~~~
san.cpp:41:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |     for (int i = 0; i < n; ++i) scanf ("%d %d", h + i, g + i);
      |                                 ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...