Submission #2210401

---

Source Code Expand

#include <algorithm>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;

struct F {
  ll X, a, b, c;
  ll upper() { return a + (c - b); }
  F down(ll t) {
    ll rem = a;
    ll over = max(0ll, t - rem);
    ll na = max(0ll, a - t);
    ll nb = min(c, b + over);
    ll nc = c;
    return {X, na, nb, nc};
  }
  F up(ll t) {
    ll rem = X - upper();
    ll over = max(0ll, t - rem);
    ll na = min(X, a + t);
    ll nb = b;
    ll nc = max(b, c - over);
    return {X, na, nb, nc};
  }
  ll at(ll x) {
    if (x <= b) {
      return a;
    }
    if (x <= c) {
      return a + (x - b);
    }
    return upper();
  }
};

int main() {
  ll X;
  int K;
  while (cin >> X >> K) {
    ++K;
    vector<ll> r(K, 0ll);
    for (int i = 1; i < K; i++) {
      cin >> r[i];
    }
    vector<F> fs(K);
    fs[0] = {X, 0ll, 0ll, X};
    for (int i = 1; i < K; i++) {
      ll dr = r[i] - r[i - 1];
      if (i % 2 == 1) {
        fs[i] = fs[i - 1].down(dr);
      } else {
        fs[i] = fs[i - 1].up(dr);
      }
    }
    int Q;
    cin >> Q;
    int k = 0;
    for (int q = 0, k = 0; q < Q; q++) {
      ll t, a;
      cin >> t >> a;
      while (k + 1 < K && r[k + 1] <= t) {
        ++k;
      }
      ll p = fs[k].at(a);
      ll dt = t - r[k];
      ll ans;
      if (k % 2 == 0) {
        ans = max(0ll, p - dt);
      } else {
        ans = min(X, p + dt);
      }
      cout << ans << endl;
    }
  }
  return 0;
}

Submission Info

Judge Result