Submission #712000

#TimeUsernameProblemLanguageResultExecution timeMemory
712000tutisPotatoes and fertilizers (LMIO19_bulves)C++17
100 / 100
167 ms21664 KiB
/*input 6 1 2 0 0 2 0 0 0 0 0 0 1 */ #pragma GCC optimize("O3") #pragma GCC target("avx2") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); using ll = long long; using ull = unsigned long long; using ld = long double; template<typename A, typename B> using omap = tree <A, B, less<A>, rb_tree_tag, tree_order_statistics_node_update>; template<typename A> using oset = tree <A, null_type, less<A>, rb_tree_tag, tree_order_statistics_node_update>; const ll mod = 1e9 + 7; ll ran(ll a, ll b) { //return a + (ll)(rng() % (b - a + 1)); return uniform_int_distribution<ll>(a, b)(rng); } ll power(ll x, ll p) { if (abs(x) >= mod) x %= mod; if (x < 0) x += mod; if (abs(p) >= mod - 1) p %= mod - 1; if (p < 0) p += mod - 1; ll r = 1; while (p) { if (p % 2) r = (r * x) % mod; x = (x * x) % mod; p /= 2; } return r; } struct por { ll x; int y; por(ll x, int y): x(x), y(y) { } }; bool operator<(const por &a, const por &b) { return a.x < b.x; } void solve() { int N; cin >> N; int a[N]; for (int i = 0; i < N; i++) { int f, b; cin >> f >> b; a[i] = f - b; } priority_queue<por>S; ll F = 1e6; ll pr = -5e11; S.push(por(pr, -F)); S.push(por(0, F)); ll v0 = F * -pr; ll sh = 0; ll sl = 0; for (int i = 0; i < N; i++) { sh += a[i]; sl--; S.push(por(sh, 2)); if (S.top().y == 1) S.pop(); else { ((por*)&S.top())->y--; } v0 += abs(pr - sh); } while (S.top().x >= sh) S.pop(); S.push(por(sh, 0)); vector<por>V; while (!S.empty()) { V.push_back(S.top()); S.pop(); } reverse(V.begin(), V.end()); for (int i = 0; i + 1 < V.size(); i++) { sl += V[i].y; v0 += (V[i + 1].x - V[i].x) * sl; } cout << v0 << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); }

Compilation message (stderr)

bulves.cpp: In function 'void solve()':
bulves.cpp:106:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<por, std::allocator<por> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |  for (int i = 0; i + 1 < V.size(); 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...