QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#185462#4906. 球球hos_lyric5 1ms3884kbC++1410.0kb2023-09-22 07:06:382023-09-22 07:06:38

Judging History

你现在查看的是最新测评结果

  • [2023-09-22 07:06:38]
  • 评测
  • 测评结果:5
  • 用时:1ms
  • 内存:3884kb
  • [2023-09-22 07:06:38]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// [0, n), 0 <= n <= 2^(6D)
template <int D> struct Set {
  int n;
  vector<unsigned long long> a[D];
  explicit Set(int n_ = 0) : n(n_) {
    static_assert(1 <= D && D <= 6, "Set: 1 <= D <= 6 must hold");
    assert(0 <= n); assert(n <= 1LL << (6 * D));
    int m = n ? n : 1;
    for (int d = 0; d < D; ++d) {
      m = (m + 63) >> 6;
      a[d].assign(m, 0);
    }
  }
  bool empty() const {
    return !a[D - 1][0];
  }
  bool contains(int x) const {
    return (a[0][x >> 6] >> (x & 63)) & 1;
  }
  void insert(int x) {
    for (int d = 0; d < D; ++d) {
      const int q = x >> 6, r = x & 63;
      a[d][q] |= 1ULL << r;
      x = q;
    }
  }
  void erase(int x) {
    for (int d = 0; d < D; ++d) {
      const int q = x >> 6, r = x & 63;
      if ((a[d][q] &= ~(1ULL << r))) break;
      x = q;
    }
  }
  // min s.t. >= x
  int next(int x) const {
    for (int d = 0; d < D; ++d) {
      const int q = x >> 6, r = x & 63;
      if (static_cast<unsigned>(q) >= a[d].size()) break;
      const unsigned long long upper = a[d][q] >> r;
      if (upper) {
        x += __builtin_ctzll(upper);
        for (int e = d - 1; e >= 0; --e) x = x << 6 | __builtin_ctzll(a[e][x]);
        return x;
      }
      x = q + 1;
    }
    return n;
  }
  // max s.t. <= x
  int prev(int x) const {
    for (int d = 0; d < D; ++d) {
      if (x < 0) break;
      const int q = x >> 6, r = x & 63;
      const unsigned long long lower = a[d][q] << (63 - r);
      if (lower) {
        x -= __builtin_clzll(lower);
        for (int e = d - 1; e >= 0; --e) x = x << 6 | (63 - __builtin_clzll(a[e][x]));
        return x;
      }
      x = q - 1;
    }
    return -1;
  }
};

////////////////////////////////////////////////////////////////////////////////


constexpr Int INF = 1001001001001001001LL;

int N;
vector<Int> T, X;

inline Int dist(int i, int j) {
  return abs(X[i] - X[j]);
}

namespace slow {
/*
  min time to put clone at X[i], completing events [0, ps[i]]
    fs[i]: event ps[i] is taken by self
    gs[i]: event ps[i] is taken by clone
*/
bool run() {
  vector<int> necks(N + 1, 0);
  for (int i = 0; i < N; ++i) {
    necks[i + 1] = necks[i] + ((T[i] + dist(i, i + 1) > T[i + 1]) ? 1 : 0);
  }
// cerr<<"necks = "<<necks<<endl;
  vector<int> ps(N + 1, 0);
  for (int i = 1; i <= N; ++i) {
    ps[i] = (i - 1 >= 1 && X[i - 1] == X[i]) ? ps[i - 1] : (i - 1);
  }
// cerr<<"ps = "<<ps<<endl;
  vector<Int> fs(N + 1, INF), gs(N + 1, INF);
  fs[0] = gs[0] = 0;
  for (int i = 1; i <= N; ++i) {
    for (int j = 0; j <= i - 2; ++j) if (necks[j+1] == necks[i-1]) {
      if (X[j] != X[i]) {
        // j -> (put i) -> j+1 -> ... -> i-1
        {
          const Int t = max({T[ps[j]] + dist(ps[j], i), T[j], fs[j] + dist(j, i)});
          if (t + dist(i, j+1) <= T[j+1]) {
            chmin(fs[i], t);
          }
        }
        {
          const Int t = max(T[j], gs[j] + dist(j, i));
          if (t + dist(i, j+1) <= T[j+1]) {
            chmin(fs[i], t);
          }
        }
      } else {
        if (max(T[ps[j]] + dist(ps[j], j+1), fs[j] + dist(j, j+1)) <= T[j+1]) {
          chmin(fs[i], fs[j]);
        }
        if (gs[j] + dist(j, j+1) <= T[j+1]) {
          chmin(fs[i], gs[j]);
        }
      }
    }
    if (X[i-1] != X[i]) {
      {
        const Int t = max({T[ps[i-1]] + dist(ps[i-1], i), T[i-1], fs[i-1] + dist(i-1, i)});
        chmin(gs[i], t);
      }
      {
        const Int t = max(T[i-1], gs[i-1] + dist(i-1, i));
        chmin(gs[i], t);
      }
    } else {
      chmin(fs[i], fs[i-1]);
      chmin(gs[i], gs[i-1]);
    }
    if (fs[i] > T[i]) fs[i] = INF;
    if (gs[i] > T[i]) gs[i] = INF;
// cerr<<COLOR("33")<<"i = "<<i<<": "<<T[i]<<" "<<X[i]<<": "<<fs[i]<<" "<<gs[i]<<COLOR()<<endl;
  }
cerr<<"fs = "<<fs<<endl;
cerr<<"gs = "<<gs<<endl;
  return (min(fs[N], gs[N]) < INF);
}
}  // slow


namespace fast {
/*
  min time to put clone at X[i], completing events [0, ps[i]]
    fs[i]: event ps[i] is taken by self
    gs[i]: event ps[i] is taken by clone
*/
bool run() {
  vector<int> necks(N + 1, 0);
  for (int i = 0; i < N; ++i) {
    necks[i + 1] = necks[i] + ((T[i] + dist(i, i + 1) > T[i + 1]) ? 1 : 0);
  }
// cerr<<"necks = "<<necks<<endl;
  vector<int> ps(N + 1, 0);
  for (int i = 1; i <= N; ++i) {
    ps[i] = (i - 1 >= 1 && X[i - 1] == X[i]) ? ps[i - 1] : (i - 1);
  }
// cerr<<"ps = "<<ps<<endl;
  
  auto xs = X;
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  const int xsLen = xs.size();
  vector<int> poss(N + 1);
  for (int i = 0; i <= N; ++i) {
    poss[i] = lower_bound(xs.begin(), xs.end(), X[i]) - xs.begin();
  }
  
  vector<pair<Int, int>> xis(N + 1);
  for (int i = 0; i <= N; ++i) {
    xis[i] = make_pair(X[i], i);
  }
  sort(xis.begin(), xis.end());
  vector<int> ids(N + 1, -1);
  for (int k = 0; k <= N; ++k) {
    ids[xis[k].second] = k;
  }
  
  vector<Int> fs(N + 1, INF), gs(N + 1, INF);
  fs[0] = gs[0] = 0;
  
  // j <= i-2 && X[j] != X[i]
  Set<4> ksDiff(N + 1);
  // j <= i-2 && X[j] == X[i]
  vector<Int> same(xsLen, INF);
  vector<int> ksSame;
  int iDiff = 2;
  
  for (int i = 1; i <= N; ++i) {
    if (i-2 >= 0) {
      if (necks[i-2] != necks[i-1]) {
        for (const int k : ksSame) {
          same[k] = INF;
        }
        ksSame.clear();
      }
      // transfer from j
      const int j = i-2;
#define i another_i
      for (; iDiff <= N; ++iDiff) {
        if (j <= iDiff-2) {
          if (necks[j+1] != necks[iDiff-1]) {
            break;
          }
          ksDiff.insert(ids[iDiff]);
        }
      }
      for (int dir = 0; dir < 2; ++dir) {
        for (; ; ) {
          const int k = dir ? ksDiff.prev(ids[j]) : ksDiff.next(ids[j]);
          if (!(0 <= k && k <= N)) break;
          const int i = xis[k].second;
          bool upd = false;
          if (j <= i-2 && necks[j+1] == necks[i-1]) {
            {
              const Int t = max({T[ps[j]] + dist(ps[j], i), T[j], fs[j] + dist(j, i)});
              if (t + dist(i, j+1) <= T[j+1]) {
// cerr<<"[fast fs] j = "<<j<<", i = "<<i<<", t = "<<t<<endl;
                upd = true;
                ksDiff.erase(k);
                chmin(fs[i], t);
              }
            }
            {
              const Int t = max(T[j], gs[j] + dist(j, i));
              if (t + dist(i, j+1) <= T[j+1]) {
// cerr<<"[fast gs] j = "<<j<<", i = "<<i<<", t = "<<t<<endl;
                upd = true;
                ksDiff.erase(k);
                chmin(fs[i], t);
              }
            }
          } else {
            upd = true;
            ksDiff.erase(k);
          }
          if (!upd) break;
        }
      }
#undef i
#define i do_not_depend_on_i
      if (max(T[ps[j]] + dist(ps[j], j+1), fs[j] + dist(j, j+1)) <= T[j+1]) {
        chmin(same[poss[j]], fs[j]);
      }
      if (gs[j] + dist(j, j+1) <= T[j+1]) {
        chmin(same[poss[j]], gs[j]);
      }
      ksSame.push_back(poss[j]);
#undef i
    }
    /*
    for (int j = 0; j <= i - 2; ++j) if (necks[j+1] == necks[i-1]) {
      if (X[j] != X[i]) {
        // j -> (put i) -> j+1 -> ... -> i-1
        {
          const Int t = max({T[ps[j]] + dist(ps[j], i), T[j], fs[j] + dist(j, i)});
          if (t + dist(i, j+1) <= T[j+1]) {
cerr<<"[brute fs] j = "<<j<<", i = "<<i<<", t = "<<t<<endl;
            // chmin(fs[i], t);
          }
        }
        {
          const Int t = max(T[j], gs[j] + dist(j, i));
          if (t + dist(i, j+1) <= T[j+1]) {
cerr<<"[brute gs] j = "<<j<<", i = "<<i<<", t = "<<t<<endl;
            // chmin(fs[i], t);
          }
        }
      }
    }
    */
    chmin(fs[i], same[poss[i]]);
    if (X[i-1] != X[i]) {
      {
        const Int t = max({T[ps[i-1]] + dist(ps[i-1], i), T[i-1], fs[i-1] + dist(i-1, i)});
        chmin(gs[i], t);
      }
      {
        const Int t = max(T[i-1], gs[i-1] + dist(i-1, i));
        chmin(gs[i], t);
      }
    } else {
      chmin(fs[i], fs[i-1]);
      chmin(gs[i], gs[i-1]);
    }
    if (fs[i] > T[i]) fs[i] = INF;
    if (gs[i] > T[i]) gs[i] = INF;
// cerr<<COLOR("33")<<"i = "<<i<<": "<<T[i]<<" "<<X[i]<<": "<<fs[i]<<" "<<gs[i]<<COLOR()<<endl;
  }
#ifdef LOCAL
cerr<<"fs = "<<fs<<endl;
cerr<<"gs = "<<gs<<endl;
#endif
  return (min(fs[N], gs[N]) < INF);
}
}  // fast


int main() {
  for (; ~scanf("%d", &N); ) {
    T.resize(N + 1);
    X.resize(N + 1);
    for (int i = 1; i <= N; ++i) {
      scanf("%lld%lld", &T[i], &X[i]);
    }
    T[0] = 0;
    X[0] = 0;
    
    const bool ans = fast::run();
    puts(ans ? "YES" : "NO");
#ifdef LOCAL
const bool brt=slow::run();
cerr<<"brt = "<<(brt?"YES":"NO")<<endl;
assert(brt==ans);
cerr<<string(80,'=')<<endl;
#endif
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 1ms
memory: 3552kb

input:

5
2 1
3 2
9 6
10 5
13 -1

output:

NO

result:

ok single line: 'NO'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

5
1 1
3 2
4 -1
6 4
10 -1

output:

NO

result:

ok single line: 'NO'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

4
16 13
18 4
20 3
21 5

output:

NO

result:

ok single line: 'NO'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

5
2 1
3 2
8 6
10 5
13 0

output:

YES

result:

ok single line: 'YES'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

5
2 1
3 2
9 6
10 5
13 0

output:

YES

result:

ok single line: 'YES'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

5
1 1
3 2
4 0
6 4
10 -1

output:

YES

result:

ok single line: 'YES'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

3
1 0
5 5
6 2

output:

YES

result:

ok single line: 'YES'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

5
2 1
6 0
7 -1
8 2
9 -2

output:

YES

result:

ok single line: 'YES'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

5
30 10
40 -10
51 9
52 8
53 20

output:

YES

result:

ok single line: 'YES'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

3
2 2
5 5
6 1

output:

YES

result:

ok single line: 'YES'

Subtask #2:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #11:

score: 0
Wrong Answer
time: 1ms
memory: 3580kb

input:

100
51823 -51823
80072 -23574
152202 48556
263343 -14629
356859 -38607
441850 -193136
442857 -192129
471412 -108145
504392 -187704
582081 -265393
680615 -220684
775219 -261463
781624 -267868
801370 -287614
899570 -166859
982377 -272221
1048767 -338611
1094930 -189414
1170308 -460152
1222829 -512673
...

output:

NO

result:

wrong answer 1st lines differ - expected: 'YES', found: 'NO'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Test #91:

score: 0
Wrong Answer
time: 0ms
memory: 3884kb

input:

5000
6 6
80 80
170 48
240 106
243 179
329 176
412 93
485 176
552 249
555 316
613 371
650 313
733 251
735 253
736 334
815 254
893 333
943 255
965 227
1022 284
1116 205
1174 320
1230 376
1318 378
1336 288
1430 212
1494 276
1562 344
1597 309
1638 350
1716 272
1793 349
1809 365
1908 306
1951 464
2037 42...

output:

NO

result:

wrong answer 1st lines differ - expected: 'YES', found: 'NO'

Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%

Subtask #7:

score: 0
Skipped

Dependency #4:

0%

Subtask #8:

score: 0
Skipped

Dependency #7:

0%