Submission #711997

#TimeUsernameProblemLanguageResultExecution timeMemory
711997tutisPotatoes and fertilizers (LMIO19_bulves)C++17
100 / 100
174 ms22368 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; } 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<pair<ll, ll>>S; ll F = 1e6; ll pr = -5e11; S.push({pr, -F}); S.push({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({sh, 2}); if (S.top().second == 1) S.pop(); else { ((pair<ll, ll>*)&S.top())->second--; // pair<ll, ll>x = S.top(); // S.pop(); // x.second--; // S.push(x); } v0 += abs(pr - sh); } while (S.top().first >= sh) S.pop(); S.push({sh, 0}); vector<pair<ll, ll>>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].second; v0 += (V[i + 1].first - V[i].first) * 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:97:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  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...