Submission #2252696


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], -1ll);
    // 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

Submission Time
Task F - Sandglass
User luma
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2519 Byte
Status WA
Exec Time 204 ms
Memory 5888 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 3
AC × 36
WA × 6
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt
Case Name Status Exec Time Memory
0_000.txt AC 1 ms 256 KB
0_001.txt AC 1 ms 256 KB
0_002.txt AC 1 ms 256 KB
1_003.txt AC 187 ms 5120 KB
1_004.txt AC 186 ms 5120 KB
1_005.txt AC 192 ms 5120 KB
1_006.txt WA 182 ms 5120 KB
1_007.txt AC 188 ms 5248 KB
1_008.txt AC 192 ms 5248 KB
1_009.txt WA 193 ms 5248 KB
1_010.txt AC 190 ms 5248 KB
1_011.txt AC 194 ms 5248 KB
1_012.txt AC 197 ms 5376 KB
1_013.txt WA 186 ms 5376 KB
1_014.txt AC 188 ms 5248 KB
1_015.txt AC 195 ms 5376 KB
1_016.txt WA 196 ms 5504 KB
1_017.txt AC 189 ms 5376 KB
1_018.txt AC 190 ms 5504 KB
1_019.txt AC 194 ms 5504 KB
1_020.txt WA 194 ms 5504 KB
1_021.txt AC 189 ms 5504 KB
1_022.txt AC 194 ms 5632 KB
1_023.txt WA 198 ms 5632 KB
1_024.txt AC 191 ms 5504 KB
1_025.txt AC 196 ms 5760 KB
1_026.txt AC 199 ms 5760 KB
1_027.txt AC 196 ms 5504 KB
1_028.txt AC 200 ms 5504 KB
1_029.txt AC 197 ms 5888 KB
1_030.txt AC 204 ms 5504 KB
1_031.txt AC 204 ms 5504 KB
1_032.txt AC 200 ms 5888 KB
1_033.txt AC 184 ms 1152 KB
1_034.txt AC 177 ms 1024 KB
1_035.txt AC 193 ms 5760 KB
1_036.txt AC 176 ms 1152 KB
1_037.txt AC 179 ms 1152 KB
1_038.txt AC 194 ms 5888 KB
1_039.txt AC 175 ms 896 KB
1_040.txt AC 181 ms 1280 KB
1_041.txt AC 197 ms 5888 KB