Submission #2697162

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <set>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(i, n) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ')
#define ITR(c,it)  for(auto it = c.begin(); it != c.end(); it++)

typedef long long ll;

const int N_MAX = 100000;

int N;
int l[N_MAX];
int r[N_MAX];
int w[N_MAX];

multiset<ll> ls, rs;
ll lf, rf;
ll ans;

void dumpDP(int i) {
  printf("i: %d\n", i);
  printf("  ls: {"); ITR(ls, it) if (*it + lf >= 0) printf("%lld, ", *it + lf); printf("}\n");
  printf("  rs: {"); ITR(rs, it) if (*it + rf <= 1e9)printf("%lld, ", *it + rf); printf("}\n");
}

void erase_one(multiset<ll> &st, ll v) {
  auto it = st.find(v);
  if (it != st.end()) st.erase(it);
}

void solve() {
  REP(i, N) w[i] = r[i] - l[i];
  ls.insert(l[0]); rs.insert(l[0]);
  ans = 0;
  lf = rf = 0;
  FOR(i, 1, N - 1) {
    // dumpDP(i);
    lf -= w[i]; rf += w[i - 1];
    ll le = *ls.rbegin() + lf;
    ll re = *rs.begin() + rf;
    ll l3 = l[i];
    // printf("  e: (%lld, %lld), l3: %lld\n", le, re, l3);
    if (l3 > re) {
      erase_one(rs, re - rf);
      ls.insert(re - lf);
      rs.insert(l3 - rf);
      rs.insert(l3 - rf);
      ans += l3 - re;
      // printf("  rs->ls: %lld, rs << %lld, ans += %lld\n", re, l3, l3 - re);
    } else if (l3 < le) {
      erase_one(ls, le - lf);
      rs.insert(le - rf);
      ls.insert(l3 - lf);
      ls.insert(l3 - lf);
      ans += le - l3;
      // printf("  ls->rs: %lld, ls << %lld, ans += %lld\n", le, l3, le - l3);
    } else {
      ls.insert(l3 - lf);
      rs.insert(l3 - rf);
      // printf("  ls << %lld rs << %lld, ans += 0\n", l3, l3);
    }
  }

  // dumpDP(N);

  printf("%lld\n", ans);
}

void input() {
  scanf("%d", &N);
  REP(i, N) {
    scanf("%d%d", l + i, r + i);
  }
}

int main() {
  input();
  solve();
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void input()’:
./Main.cpp:75:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N);
                  ^
./Main.cpp:77:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", l + i, r + i);
                                ^

Judge Result