oj.uz

Submission #707970

# Submission time Handle Problem Language Result Execution time Memory
707970 2023-03-10T15:48:16 Z pauloamed Potatoes and fertilizers (LMIO19_bulves) C++14
100 / 100
 445 ms 28836 KB 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define mp make_pair
 
template<typename T> struct OffsetPq : 
  priority_queue<int,vector<int>,T> {
  int offset = 0;
 
  void push(int x) {
    priority_queue<int,vector<int>, T>::push(x - offset);
  }
 
  int top() {
    return priority_queue<int,vector<int>,T>::top() + offset;
  }
 
  void addToOffset(int x) {
    offset += x;
  }
};
 
struct PiecewiseConvex{
  int a, b; // ax + b
  OffsetPq<less<int>> slopeChangeUntil0;
  OffsetPq<greater<int>> slopeChangeAfter0;
 
  PiecewiseConvex(int _a=0, int _b=0):a(_a), b(_b){}
  
  void merge(PiecewiseConvex &st){
    a += st.a, b += st.b;
 
    auto addToPQs = [&](int x) {
      if(slopeChangeAfter0.size() && slopeChangeAfter0.top() <= x)
        slopeChangeAfter0.push(x);
      else slopeChangeUntil0.push(x);
    };
 
    while(st.slopeChangeUntil0.size()) {
      addToPQs(st.slopeChangeUntil0.top());
      st.slopeChangeUntil0.pop();
    }
    
    while(st.slopeChangeAfter0.size()) {
      addToPQs(st.slopeChangeAfter0.top());
      st.slopeChangeAfter0.pop();
    }
 
    if(a < 0) {
      while(-a > slopeChangeUntil0.size()) {
        int x = slopeChangeAfter0.top();
        slopeChangeAfter0.pop();
        slopeChangeUntil0.push(x);
      }
  
      while(-a < slopeChangeUntil0.size()) {
        int x = slopeChangeUntil0.top();
        slopeChangeUntil0.pop();
        slopeChangeAfter0.push(x);
      }
    } else if(a >= 0) {
      while(slopeChangeUntil0.size()) {
        int x = slopeChangeUntil0.top();
        slopeChangeUntil0.pop();
        slopeChangeAfter0.push(x);
      }
    }

  }

  void min_pref() {
    a = min(a, 0LL);
    slopeChangeAfter0 = OffsetPq<greater<int>>();
  }
 
  void min_op(int h0, int h1) {
    // f(x) = g(t), t - x <= h0, x - t <= h1
    b += h0 * a;
    slopeChangeUntil0.addToOffset(-h0);
    slopeChangeAfter0.addToOffset(h1);
  }
 
  void print(){
    cout << a << " " << b << "\n";
    {
      auto x = slopeChangeUntil0;
      vector<int> v;
      while(x.size()) {
        v.push_back(x.top()); x.pop();
      }
      reverse(v.begin(), v.end());
      for(auto y : v) cout << y << " "; cout << endl;
    }
    {
      auto x = slopeChangeAfter0;
      vector<int> v;
      while(x.size()) {
        v.push_back(x.top()); x.pop();
      }
      for(auto y : v) cout << y << " "; cout << endl;
    }
    cout << "------------------------\n";
  }
};
 
 
PiecewiseConvex buildAbs(int a){
  // builds |a - x|
  PiecewiseConvex st(-1, a);
  st.slopeChangeUntil0.push(a);
  st.slopeChangeAfter0.push(a);
  return st;
}
 
int32_t main(){
  int n; cin >> n;
  vector<int> a(n), b(n);
  for(int i = 0; i < n; ++i) cin >> a[i] >> b[i];

  vector<int> dif;
  for(int i = 0; i < n; ++i)
    dif.push_back(a[i] - b[i]);
  
  vector<int> d = {0};
  for(int i = 0; i < n; ++i) {
    d.push_back(dif[i] + d.back());
  }

  // for(auto x : d) cout << x << " ";
  // cout << endl;

  // turn d into non-dec
  
  PiecewiseConvex dp = buildAbs(d[0]);
  dp.min_pref();
  for(int i = 1; i < d.size(); ++i) {
    // cout << "processing " << i << ": " << d[i] << endl;

    PiecewiseConvex transition;
    if(d[i] < d[0]) {
      transition = PiecewiseConvex(1, -d[i]);
    } else {
      transition = buildAbs(d[i]);
    }

    dp.merge(transition);
    dp.min_pref();

    // dp.print();
  }

  // cout << d.back() << "\n";

  int sum_b = 0;
  int still_slope = 0;
  while(dp.slopeChangeUntil0.size()) {
    int pt = dp.slopeChangeUntil0.top();
    dp.slopeChangeUntil0.pop();

    if(pt <= d.back()) sum_b += pt;
    else still_slope++;
  }
 
  cout << dp.b - sum_b - still_slope * d.back() << "\n";
}

Compilation message

bulves.cpp: In member function 'void PiecewiseConvex::merge(PiecewiseConvex&)':
bulves.cpp:51:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::priority_queue<long long int, std::vector<long long int>, std::less<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |       while(-a > slopeChangeUntil0.size()) {
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bulves.cpp:57:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::priority_queue<long long int, std::vector<long long int>, std::less<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |       while(-a < slopeChangeUntil0.size()) {
      |             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
bulves.cpp: In member function 'void PiecewiseConvex::print()':
bulves.cpp:93:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   93 |       for(auto y : v) cout << y << " "; cout << endl;
      |       ^~~
bulves.cpp:93:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   93 |       for(auto y : v) cout << y << " "; cout << endl;
      |                                         ^~~~
bulves.cpp:101:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  101 |       for(auto y : v) cout << y << " "; cout << endl;
      |       ^~~
bulves.cpp:101:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  101 |       for(auto y : v) cout << y << " "; cout << endl;
      |                                         ^~~~
bulves.cpp: In function 'int32_t main()':
bulves.cpp:137:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   for(int i = 1; i < d.size(); ++i) {
      |                  ~~^~~~~~~~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 28 ms 2248 KB Output is correct
5 Correct 69 ms 4184 KB Output is correct
6 Correct 220 ms 11120 KB Output is correct
7 Correct 294 ms 18080 KB Output is correct
8 Correct 379 ms 22040 KB Output is correct
9 Correct 268 ms 18264 KB Output is correct
10 Correct 288 ms 22044 KB Output is correct
11 Correct 256 ms 22064 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 28 ms 2248 KB Output is correct
5 Correct 69 ms 4184 KB Output is correct
6 Correct 220 ms 11120 KB Output is correct
7 Correct 294 ms 18080 KB Output is correct
8 Correct 379 ms 22040 KB Output is correct
9 Correct 268 ms 18264 KB Output is correct
10 Correct 288 ms 22044 KB Output is correct
11 Correct 256 ms 22064 KB Output is correct
12 Correct 100 ms 5712 KB Output is correct
13 Correct 251 ms 17492 KB Output is correct
14 Correct 298 ms 24860 KB Output is correct
15 Correct 383 ms 27044 KB Output is correct
16 Correct 367 ms 26268 KB Output is correct
17 Correct 262 ms 24168 KB Output is correct
18 Correct 2 ms 440 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 436 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 436 KB Output is correct
11 Correct 2 ms 440 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 3 ms 440 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 3 ms 468 KB Output is correct
16 Correct 3 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 3 ms 468 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 436 KB Output is correct
11 Correct 28 ms 2248 KB Output is correct
12 Correct 69 ms 4184 KB Output is correct
13 Correct 220 ms 11120 KB Output is correct
14 Correct 294 ms 18080 KB Output is correct
15 Correct 379 ms 22040 KB Output is correct
16 Correct 268 ms 18264 KB Output is correct
17 Correct 288 ms 22044 KB Output is correct
18 Correct 256 ms 22064 KB Output is correct
19 Correct 100 ms 5712 KB Output is correct
20 Correct 251 ms 17492 KB Output is correct
21 Correct 298 ms 24860 KB Output is correct
22 Correct 383 ms 27044 KB Output is correct
23 Correct 367 ms 26268 KB Output is correct
24 Correct 262 ms 24168 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 3 ms 440 KB Output is correct
27 Correct 3 ms 468 KB Output is correct
28 Correct 3 ms 468 KB Output is correct
29 Correct 3 ms 468 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 3 ms 468 KB Output is correct
32 Correct 2 ms 440 KB Output is correct
33 Correct 108 ms 7360 KB Output is correct
34 Correct 266 ms 19884 KB Output is correct
35 Correct 439 ms 28780 KB Output is correct
36 Correct 408 ms 26420 KB Output is correct
37 Correct 381 ms 26904 KB Output is correct
38 Correct 445 ms 28792 KB Output is correct
39 Correct 289 ms 24976 KB Output is correct
40 Correct 313 ms 23476 KB Output is correct
41 Correct 261 ms 23972 KB Output is correct
42 Correct 267 ms 24028 KB Output is correct
43 Correct 291 ms 24052 KB Output is correct
44 Correct 268 ms 24120 KB Output is correct
45 Correct 425 ms 28836 KB Output is correct
46 Correct 312 ms 24340 KB Output is correct
47 Correct 263 ms 21304 KB Output is correct