Submission #2252690

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = long long;



int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  ll x, k; cin >> x >> k;
  vector<ll> r(k + 2), diff(k + 2);
  for(int i = 0; i < k; i++) {
    cin >> r[i + 1];
    diff[i + 1] = diff[i] + (i % 2 ? 1 : -1) * (r[i + 1] - r[i]);

    // cerr << r[i + 1] << ", " << diff[i + 1] << endl;
  }
  // sentinel
  r[k + 1] = 1e9 + 19;

  vector<ll> mi(k + 1, x + 1), ma(k + 1, -1);
  mi[0] = 0; ma[0] = x;
  ll rmi = 0, rma = x;
  vector<ll> rvaltop(k + 1), rvalbottom(k + 1);
  bool stop = 0;
  for(int i = 1; i <= k; i++) {
    int df = r[i] - r[i - 1];
    if(mi[i - 1] <= x) mi[i] = mi[i - 1];
    if(ma[i - 1] >= 0) ma[i] = ma[i - 1];
    if(i % 2) { // down
      rmi -= df;
      rma -= df;
    } else { // up
      rmi += df;
      rma += df;
    }
    if(rmi < 0) {
      if(mi[i] <= x) mi[i] += -rmi;
      rmi = 0;
    }
    if(rma < 0) {
      if(ma[i] >= 0) ma[i] += -rma;
      rma = 0;
    }
    if(rmi > x) {
      if(mi[i] <= x) mi[i] -= rmi - x;
      rmi = x;
    }
    if(rma > x) {
      if(ma[i] >= 0) ma[i] -= rma - x;
      rma = x;
    }
    rvalbottom[i] = rmi;
    rvaltop[i] = rma;
    if(mi[i] > ma[i]) mi[i] = x + 1, ma[i] = -1;
    mi[i] = min(mi[i], x + 1);
    ma[i] = max(ma[i], -1);
    // cerr << endl << "i : " << i << endl;
    // cerr << "mi: " << mi[i] << " , ma: " << ma[i] << endl;
    // cerr << "rmi: " << rmi << " , rma: " << rma << endl;
  }
  // cerr << endl;

  ll q; cin >> q;
  for(int i = 0; i < q; i++) {
    ll t, a; cin >> t >> a;
    int pmi = upper_bound(begin(mi), end(mi), a) - begin(mi) - 1;
    int pma = upper_bound(begin(ma), end(ma), a, greater<ll>()) - begin(ma) - 1;
    int p = min(pmi, pma);
    int g = upper_bound(begin(r), end(r), t) - begin(r) - 1;
    ll gt = t - r[g];
    int dec = 1 - g % 2;
    int tp = pmi > pma;

    // cerr << endl << "i : " << i << endl;
    // cerr << "g: " << g << " , p: " << p << endl;
    // cerr << "pmi: " << pmi << " , pma: " << pma << endl;
    // cerr << "gt: " << gt << " , dec: " << dec << endl;
    ll val;
    if(p + 1 <= g) {
      // not unique-er
      // no identity
      // HEIBON

      // cerr << "not unque " << endl;
      val = (tp ? rvaltop[g] : rvalbottom[g]) + (dec ? -1 : 1) * gt;
    } else {
      val = a + diff[g] + (dec ? -1 : 1) * gt;
    }
    val = min(val, x);
    val = max(val, 0ll);
    cout << val << endl;
  }
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:56:26: error: no matching function for call to ‘max(__gnu_cxx::__alloc_traits<std::allocator<long long int> >::value_type&, int)’
     ma[i] = max(ma[i], -1);
                          ^
In file included from /usr/include/c++/5/bits/char_traits.h:39:0,
                 from /usr/include/c++/5/ios:40,
                 from /usr/include/c++/5/istream:38,
                 from /usr/include/c++/5/sstream:38,
                 from /usr/include/c++/5/complex:45,
                 from /usr/include/c++/5/ccomplex:38,
                 from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:52,
                 from ./Main.cpp:1:
/usr/include/c++/5/bits/stl_algobase.h:219:5: note: candidate: template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)
     max(const _Tp& __a, const _Tp& __b)
     ^
/usr/include/c++/5/bits/stl_algobase.h:219:5: note:   template argument deduction/substitution failed:
./Main.cpp:56:26: note:   deduced conflicting types for par...