oj.uz

Submission #707955

# Submission time Handle Problem Language Result Execution time Memory
707955 2023-03-10T15:15:45 Z pauloamed Potatoes and fertilizers (LMIO19_bulves) C++14
24 / 100
 366 ms 26908 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() {
    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;
  while(dp.slopeChangeUntil0.size()) {
    int pt = dp.slopeChangeUntil0.top();
    dp.slopeChangeUntil0.pop();

    if(pt <= d.back()) sum_b += pt;
  }
 
  cout << dp.b - sum_b << "\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:92:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   92 |       for(auto y : v) cout << y << " "; cout << endl;
      |       ^~~
bulves.cpp:92:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   92 |       for(auto y : v) cout << y << " "; cout << endl;
      |                                         ^~~~
bulves.cpp:100:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  100 |       for(auto y : v) cout << y << " "; cout << endl;
      |       ^~~
bulves.cpp:100:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  100 |       for(auto y : v) cout << y << " "; cout << endl;
      |                                         ^~~~
bulves.cpp: In function 'int32_t main()':
bulves.cpp:136: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]
  136 |   for(int i = 1; i < d.size(); ++i) {
      |                  ~~^~~~~~~~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 25 ms 2480 KB Output is correct
5 Correct 58 ms 4908 KB Output is correct
6 Correct 208 ms 14556 KB Output is correct
7 Correct 278 ms 24864 KB Output is correct
8 Correct 366 ms 26908 KB Output is correct
9 Correct 238 ms 22332 KB Output is correct
10 Correct 242 ms 24032 KB Output is correct
11 Correct 254 ms 23948 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 25 ms 2480 KB Output is correct
5 Correct 58 ms 4908 KB Output is correct
6 Correct 208 ms 14556 KB Output is correct
7 Correct 278 ms 24864 KB Output is correct
8 Correct 366 ms 26908 KB Output is correct
9 Correct 238 ms 22332 KB Output is correct
10 Correct 242 ms 24032 KB Output is correct
11 Correct 254 ms 23948 KB Output is correct
12 Incorrect 98 ms 7432 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -