QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#185462 | #4906. 球球 | hos_lyric | 5 | 1ms | 3884kb | C++14 | 10.0kb | 2023-09-22 07:06:38 | 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%