Submission #3235746


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
  each(x,vec) is >> x;
  return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
  rep(i,vec.size()) {
    if (i) os << " ";
    os << vec[i];
  }
  return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
  rep(i,vec.size()) {
    if (i) os << endl;
    os << vec[i];
  }
  return os;
}

template <class Monoid>
class SegmentTree {
  using T = typename Monoid::type;
  const int size_, n;
  std::vector<T> data;
  int expand(int m) const { return m <= 1 ? 1 : expand((m + 1) / 2) * 2; }
public:
  SegmentTree() : SegmentTree(0) {}
  SegmentTree(const std::vector<T> &vec) :
    size_(vec.size()), n(expand(size_)), data(n * 2, Monoid::id()) {
    std::copy(begin(vec), end(vec), begin(data) + n);
    for (int i = n - 1; i >= 0; --i) {
      data[i] = Monoid::op(data[i * 2 + 0], data[i * 2 + 1]);
    }
  }
  SegmentTree(const int count, const T &value = Monoid::id()) :
    SegmentTree(std::vector<T>(count, value)) {}
  int size() const { return size_; }
  void update(int pos, const T &value) {
    assert (0 <= pos && pos < size_); // assertion
    data[pos += n] = value;
    while (pos /= 2) {
      data[pos] = Monoid::op(data[pos * 2], data[pos * 2 + 1]);
    }
  }
  T find(int l, int r) const {
    assert (0 <= l && l <= r && r <= size_); // assertion
    l += n; r += n;
    T res1 = Monoid::id(), res2 = Monoid::id();
    while (l != r) {
      if (l % 2) res1 = Monoid::op(res1, data[l++]);
      if (r % 2) res2 = Monoid::op(data[--r], res2);
      l /= 2; r /= 2;
    }
    return Monoid::op(res1, res2);
  }
  using value_type = T;
  using update_type = T;
};

struct Min {
  using type = ll;
  static type id() { return linf; }
  static type op(const type &l, const type &r) { return min(l, r); }
};
struct Max {
  using type = ll;
  static type id() { return -linf; }
  static type op(const type &l, const type &r) { return max(l, r); }
};
struct Sum {
  using type = ll;
  static type id() { return 0; }
  static type op(const type &l, const type &r) { return l + r; }
};

const ll mod = 1e9+7;
ll mul(ll a, ll b) {
  return a * b % mod;
}
ll mul(initializer_list<ll> t) {
  ll res = 1;
  each(v, t) res = mul(res, v);
  return res;
}
ll add(ll a, ll b) {
  return (a + b) % mod;
}
ll add(initializer_list<ll> t) {
  ll res = 0;
  each(v, t) res = add(res, v);
  return res;
}
ll sub(ll a, ll b) {
  return (a - b + mod) % mod;
}
ll sub(initializer_list<ll> t) {
  auto it = t.begin();
  ll res = *(it++);
  while (it != t.end()) {
    res = sub(res, *(it++));
  }
  return res;
}
ll inv(ll n);
ll power(ll x, ll n) {
  if (n < 0) return inv(power(x, -n));
  ll res = 1;
  for (ll i = 1; i <= n; i <<= 1) {
    if (i & n) res = mul(res, x);
    x = mul(x, x);
  }
  return res;
}
ll inv(ll n) {
  return power(n, mod-2);
}
ll divi(ll a, ll b) {
  return mul(a, inv(b));
}
ll divi(initializer_list<ll> t) {
  auto it = t.begin();
  ll res = *(it++);
  while (it != t.end()) {
    res = divi(res, *(it++));
  }
  return res;
}
vector<ll> fact;
void init_fact(ll n) {
  fact.assign(n+1, 1);
  FOR(i, 1, fact.size()) {
    fact[i] = mul(fact[i-1], i);
  }
}

ll comb(ll n, ll r) {
  if (r < 0) return 0;
  if (r > n) return 0;
  return divi(fact[n], mul(fact[r], fact[n-r]));
}

using Row = vector<ll>;
using Matrix = vector<Row>;
Matrix E(ll n) {
  Matrix res(n, Row(n, 0));
  rep(i, n) res[i][i] = 1;
  return res;
}
Matrix mul(const Matrix& A, const Matrix& B) {
  const ll n = A.size(), m = A[0].size(), l = B[0].size();
  assert(m == B.size());
  Matrix res(n, Row(l, 0));
  rep(i, n) rep(j, m) rep(k, l) {
    res[i][k] = add(res[i][k], mul(A[i][j], B[j][k]));
  }
  return res;
}
Row mul(const Matrix& A, const Row& x) {
  Matrix tx(x.size());
  rep(i, x.size()) tx[i] = Row(1, x[i]);
  tx = mul(A, tx);
  Row res(x.size());
  rep(i, x.size()) res[i] = tx[i][0];
  return res;
}
Matrix power(Matrix A, ll n) {
  assert(A.size() == A[0].size());
  Matrix res = E(A.size());
  for (ll i = 1; i <= n; i <<= 1) {
    if (i & n) res = mul(res, A);
    A = mul(A, A);
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n; cin >> n;
  vector<P> v;
  v.eb(-100000, -100000+1);
  rep(i, n) {
    ll x, d; cin >> x >> d;
    v.eb(x-d, x+d+1);
    // rep(j, x-d, x+d+1) {
    //   X.pb(j);
    // }
  }
  n = v.size();
  const ll m = 2001;
  vector<SegmentTree<Sum>> dp(2, SegmentTree<Sum>(m));
  dp[0].update(0, 1);
  rep(i, 1, n) {
    ll l, r; tie(l, r) = v[i];
    rep(j, r-l) {
      ll pos = min(v[i-1].second-v[i-1].first+1, max(l+j-v[i-1].first, 0LL));
      ll val = dp[i+1&1].find(0, pos);
      // cout << pos << " " << j << " " << val << endl;
      dp[i&1].update(j, val);
    }
  }
  cout << dp[(n-1)&1].find(0, m) << endl;
}

Submission Info

Submission Time
Task D - ぽよぽよ
User drafear
Language C++14 (GCC 5.4.1)
Score 0
Code Size 5805 Byte
Status RE
Exec Time 132 ms
Memory 512 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 5
WA × 44
RE × 4
Set Name Test Cases
All 00-sample-00, 00-sample-01, handmade-00, largest-00, largest-01, largest-02, largest-03, largest-04, largest-05, random-00-0499, random-01-0439, random-02-0683, random-03-0329, random-04-0177, random-05-0106, random-06-0659, random-07-0421, random-08-0087, random-09-0455, random-10-0777, random-11-0148, random-12-0737, random-13-0119, random-14-0513, random-15-0237, random-16-0988, random-17-0322, random-18-0152, random-19-0612, random-20-0789, random-21-0213, random-22-0291, random-23-0159, random-24-0618, random-25-0601, random-26-0726, random-27-0491, random-28-0324, random-29-0429, random-30-0825, random-31-0645, random-32-0108, random-33-0203, random-34-0802, random-35-0155, random-36-0458, random-37-0674, random-38-0551, random-39-0063, random-40-0026, random-41-0545, sample-00, sample-01
Case Name Status Exec Time Memory
00-sample-00 AC 1 ms 384 KB
00-sample-01 AC 1 ms 384 KB
handmade-00 AC 1 ms 384 KB
largest-00 RE 132 ms 512 KB
largest-01 RE 116 ms 384 KB
largest-02 RE 102 ms 384 KB
largest-03 WA 40 ms 384 KB
largest-04 RE 131 ms 384 KB
largest-05 WA 39 ms 384 KB
random-00-0499 WA 1 ms 384 KB
random-01-0439 WA 1 ms 384 KB
random-02-0683 WA 1 ms 384 KB
random-03-0329 WA 1 ms 384 KB
random-04-0177 WA 1 ms 384 KB
random-05-0106 WA 1 ms 384 KB
random-06-0659 WA 2 ms 384 KB
random-07-0421 WA 2 ms 384 KB
random-08-0087 WA 1 ms 384 KB
random-09-0455 WA 2 ms 384 KB
random-10-0777 WA 2 ms 384 KB
random-11-0148 WA 1 ms 384 KB
random-12-0737 WA 2 ms 384 KB
random-13-0119 WA 1 ms 384 KB
random-14-0513 WA 2 ms 384 KB
random-15-0237 WA 2 ms 384 KB
random-16-0988 WA 2 ms 384 KB
random-17-0322 WA 2 ms 384 KB
random-18-0152 WA 1 ms 384 KB
random-19-0612 WA 2 ms 384 KB
random-20-0789 WA 2 ms 384 KB
random-21-0213 WA 2 ms 384 KB
random-22-0291 WA 2 ms 384 KB
random-23-0159 WA 1 ms 384 KB
random-24-0618 WA 2 ms 384 KB
random-25-0601 WA 2 ms 384 KB
random-26-0726 WA 2 ms 384 KB
random-27-0491 WA 2 ms 384 KB
random-28-0324 WA 3 ms 512 KB
random-29-0429 WA 2 ms 384 KB
random-30-0825 WA 3 ms 384 KB
random-31-0645 WA 2 ms 384 KB
random-32-0108 WA 2 ms 384 KB
random-33-0203 WA 2 ms 384 KB
random-34-0802 WA 3 ms 384 KB
random-35-0155 WA 2 ms 384 KB
random-36-0458 WA 2 ms 384 KB
random-37-0674 WA 3 ms 384 KB
random-38-0551 WA 2 ms 384 KB
random-39-0063 WA 1 ms 384 KB
random-40-0026 WA 1 ms 384 KB
random-41-0545 WA 3 ms 384 KB
sample-00 AC 1 ms 384 KB
sample-01 AC 1 ms 384 KB