QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#106739 | #6326. Make Convex Sequence | maspy | AC ✓ | 29ms | 15788kb | C++23 | 15.3kb | 2023-05-19 01:11:55 | 2023-05-19 01:11:56 |
Judging History
answer
#line 1 "/home/maspy/compro/library/my_template.hpp"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
#define vv(type, name, h, ...) \
vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) \
vector<vector<vector<type>>> name( \
h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name( \
a, vector<vector<vector<type>>>( \
b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define FOR4_R(i, a, b, c) for (ll i = (b)-1; i >= ll(a); i -= (c))
#define overload4(a, b, c, d, e, ...) e
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) \
overload4(__VA_ARGS__, FOR4_R, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_subset(t, s) for (ll t = s; t >= 0; t = (t == 0 ? -1 : (t - 1) & s))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define stoi stoll
template <typename T, typename U>
T SUM(const vector<U> &A) {
T sum = 0;
for (auto &&a: A) sum += a;
return sum;
}
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end())
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
template <typename T>
T pick(deque<T> &que) {
T a = que.front();
que.pop_front();
return a;
}
template <typename T>
T pick(pq<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T pick(pqg<T> &que) {
assert(que.size());
T a = que.top();
que.pop();
return a;
}
template <typename T>
T pick(vc<T> &que) {
assert(que.size());
T a = que.back();
que.pop_back();
return a;
}
template <typename T, typename U>
T ceil(T x, U y) {
return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U>
T floor(T x, U y) {
return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T, typename U>
pair<T, T> divmod(T x, U y) {
T q = floor(x, y);
return {q, x - q * y};
}
template <typename F>
ll binary_search(F check, ll ok, ll ng) {
assert(check(ok));
while (abs(ok - ng) > 1) {
auto x = (ng + ok) / 2;
tie(ok, ng) = (check(x) ? mp(x, ng) : mp(ok, x));
}
return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
FOR(iter) {
double x = (ok + ng) / 2;
tie(ok, ng) = (check(x) ? mp(x, ng) : mp(ok, x));
}
return (ok + ng) / 2;
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
vc<int> s_to_vi(const string &S, char first_char) {
vc<int> A(S.size());
FOR(i, S.size()) { A[i] = S[i] - first_char; }
return A;
}
template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
int N = A.size();
vector<T> B(N + 1);
FOR(i, N) { B[i + 1] = B[i] + A[i]; }
if (off == 0) B.erase(B.begin());
return B;
}
template <typename CNT, typename T>
vc<CNT> bincount(const vc<T> &A, int size) {
vc<CNT> C(size);
for (auto &&x: A) { ++C[x]; }
return C;
}
// stable
template <typename T>
vector<int> argsort(const vector<T> &A) {
vector<int> ids(A.size());
iota(all(ids), 0);
sort(all(ids),
[&](int i, int j) { return A[i] < A[j] || (A[i] == A[j] && i < j); });
return ids;
}
// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
int n = len(I);
vc<T> B(n);
FOR(i, n) B[i] = A[I[i]];
return B;
}
#line 1 "/home/maspy/compro/library/other/io.hpp"
// based on yosupo's fastio
#include <unistd.h>
namespace detail {
template <typename T, decltype(&T::is_modint) = &T::is_modint>
std::true_type check_value(int);
template <typename T>
std::false_type check_value(long);
} // namespace detail
template <typename T>
struct is_modint : decltype(detail::check_value<T>(0)) {};
template <typename T>
using is_modint_t = enable_if_t<is_modint<T>::value>;
template <typename T>
using is_not_modint_t = enable_if_t<!is_modint<T>::value>;
struct Scanner {
FILE *fp;
char line[(1 << 15) + 1];
size_t st = 0, ed = 0;
void reread() {
memmove(line, line + st, ed - st);
ed -= st;
st = 0;
ed += fread(line + ed, 1, (1 << 15) - ed, fp);
line[ed] = '\0';
}
bool succ() {
while (true) {
if (st == ed) {
reread();
if (st == ed) return false;
}
while (st != ed && isspace(line[st])) st++;
if (st != ed) break;
}
if (ed - st <= 50) {
bool sep = false;
for (size_t i = st; i < ed; i++) {
if (isspace(line[i])) {
sep = true;
break;
}
}
if (!sep) reread();
}
return true;
}
template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
bool read_single(T &ref) {
if (!succ()) return false;
while (true) {
size_t sz = 0;
while (st + sz < ed && !isspace(line[st + sz])) sz++;
ref.append(line + st, sz);
st += sz;
if (!sz || st != ed) break;
reread();
}
return true;
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
bool read_single(T &ref) {
if (!succ()) return false;
bool neg = false;
if (line[st] == '-') {
neg = true;
st++;
}
ref = T(0);
while (isdigit(line[st])) { ref = 10 * ref + (line[st++] & 0xf); }
if (neg) ref = -ref;
return true;
}
template <class T, is_modint_t<T> * = nullptr>
bool read_single(T &ref) {
long long val = 0;
bool f = read_single(val);
ref = T(val);
return f;
}
bool read_single(double &ref) {
string s;
if (!read_single(s)) return false;
ref = std::stod(s);
return true;
}
bool read_single(char &ref) {
string s;
if (!read_single(s) || s.size() != 1) return false;
ref = s[0];
return true;
}
template <class T>
bool read_single(vector<T> &ref) {
for (auto &d: ref) {
if (!read_single(d)) return false;
}
return true;
}
template <class T, class U>
bool read_single(pair<T, U> &p) {
return (read_single(p.first) && read_single(p.second));
}
template <class A, class B, class C>
bool read_single(tuple<A, B, C> &p) {
return (read_single(get<0>(p)) && read_single(get<1>(p))
&& read_single(get<2>(p)));
}
template <class A, class B, class C, class D>
bool read_single(tuple<A, B, C, D> &p) {
return (read_single(get<0>(p)) && read_single(get<1>(p))
&& read_single(get<2>(p)) && read_single(get<3>(p)));
}
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
bool f = read_single(h);
assert(f);
read(t...);
}
Scanner(FILE *fp) : fp(fp) {}
};
struct Printer {
Printer(FILE *_fp) : fp(_fp) {}
~Printer() { flush(); }
static constexpr size_t SIZE = 1 << 15;
FILE *fp;
char line[SIZE], small[50];
size_t pos = 0;
void flush() {
fwrite(line, 1, pos, fp);
pos = 0;
}
void write(const char &val) {
if (pos == SIZE) flush();
line[pos++] = val;
}
template <class T, enable_if_t<is_integral<T>::value, int> = 0>
void write(T val) {
if (pos > (1 << 15) - 50) flush();
if (val == 0) {
write('0');
return;
}
if (val < 0) {
write('-');
val = -val; // todo min
}
size_t len = 0;
while (val) {
small[len++] = char(0x30 | (val % 10));
val /= 10;
}
for (size_t i = 0; i < len; i++) { line[pos + i] = small[len - 1 - i]; }
pos += len;
}
void write(const string &s) {
for (char c: s) write(c);
}
void write(const char *s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) write(s[i]);
}
void write(const double &x) {
ostringstream oss;
oss << fixed << setprecision(15) << x;
string s = oss.str();
write(s);
}
void write(const long double &x) {
ostringstream oss;
oss << fixed << setprecision(15) << x;
string s = oss.str();
write(s);
}
template <class T, is_modint_t<T> * = nullptr>
void write(T &ref) {
write(ref.val);
}
template <class T>
void write(const vector<T> &val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write(' ');
write(val[i]);
}
}
template <class T, class U>
void write(const pair<T, U> &val) {
write(val.first);
write(' ');
write(val.second);
}
template <class A, class B, class C>
void write(const tuple<A, B, C> &val) {
auto &[a, b, c] = val;
write(a), write(' '), write(b), write(' '), write(c);
}
template <class A, class B, class C, class D>
void write(const tuple<A, B, C, D> &val) {
auto &[a, b, c, d] = val;
write(a), write(' '), write(b), write(' '), write(c), write(' '), write(d);
}
template <class A, class B, class C, class D, class E>
void write(const tuple<A, B, C, D, E> &val) {
auto &[a, b, c, d, e] = val;
write(a), write(' '), write(b), write(' '), write(c), write(' '), write(d), write(' '), write(e);
}
template <class A, class B, class C, class D, class E, class F>
void write(const tuple<A, B, C, D, E, F> &val) {
auto &[a, b, c, d, e, f] = val;
write(a), write(' '), write(b), write(' '), write(c), write(' '), write(d), write(' '), write(e), write(' '), write(f);
}
template <class T, size_t S>
void write(const array<T, S> &val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) write(' ');
write(val[i]);
}
}
void write(i128 val) {
string s;
bool negative = 0;
if(val < 0){
negative = 1;
val = -val;
}
while (val) {
s += '0' + int(val % 10);
val /= 10;
}
if(negative) s += "-";
reverse(all(s));
if (len(s) == 0) s = "0";
write(s);
}
};
Scanner scanner = Scanner(stdin);
Printer printer = Printer(stdout);
void flush() { printer.flush(); }
void print() { printer.write('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
printer.write(head);
if (sizeof...(Tail)) printer.write(' ');
print(forward<Tail>(tail)...);
}
void read() {}
template <class Head, class... Tail>
void read(Head &head, Tail &... tail) {
scanner.read(head);
read(tail...);
}
#define INT(...) \
int __VA_ARGS__; \
read(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
read(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
read(__VA_ARGS__)
#define CHAR(...) \
char __VA_ARGS__; \
read(__VA_ARGS__)
#define DBL(...) \
double __VA_ARGS__; \
read(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
read(name)
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
read(name)
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
#line 3 "main.cpp"
template <typename T>
vector<int> ConvexHull(vector<pair<T, T>>& XY, string mode = "full",
bool inclusive = false, bool sorted = false) {
assert(mode == "full" || mode == "lower" || mode == "upper");
ll N = XY.size();
if (N == 1) return {0};
if (N == 2) return {0, 1};
vc<int> I = argsort(XY);
auto check = [&](ll i, ll j, ll k) -> bool {
auto xi = XY[i].fi, yi = XY[i].se;
auto xj = XY[j].fi, yj = XY[j].se;
auto xk = XY[k].fi, yk = XY[k].se;
auto dx1 = xj - xi, dy1 = yj - yi;
auto dx2 = xk - xj, dy2 = yk - yj;
ll det = dx1 * dy2 - dy1 * dx2;
return (inclusive ? det >= 0 : det > 0);
};
auto calc = [&]() {
vector<int> P;
for (auto&& k: I) {
while (P.size() > 1) {
auto i = P[P.size() - 2];
auto j = P[P.size() - 1];
if (check(i, j, k)) break;
P.pop_back();
}
P.eb(k);
}
return P;
};
vc<int> P;
if (mode == "full" || mode == "lower") {
vc<int> Q = calc();
P.insert(P.end(), all(Q));
}
if (mode == "full" || mode == "upper") {
if (!P.empty()) P.pop_back();
reverse(all(I));
vc<int> Q = calc();
P.insert(P.end(), all(Q));
}
if (mode == "upper") reverse(all(P));
if (len(P) >= 2 && P[0] == P.back()) P.pop_back();
return P;
}
void solve() {
LL(N);
VEC(ll, LO, N);
VEC(ll, HI, N);
vc<pi> XY;
FOR(i, N) { XY.eb(i, HI[i]); }
auto I = ConvexHull<ll>(XY, "lower", 0, 1);
FOR(k, len(I) - 1) {
auto [x1, y1] = XY[I[k]];
auto [x2, y2] = XY[I[k + 1]];
FOR(x, x1 + 1, x2) {
// y1+(y2-y1)/(x2-x1)*(x-x1) >= LO[x]
ll lhs = y1 * (x2 - x1) + (y2 - y1) * (x - x1);
ll rhs = LO[x] * (x2 - x1);
if (lhs < rhs) return No();
}
}
Yes();
}
signed main() {
cout << fixed << setprecision(15);
ll T = 1;
// LL(T);
FOR(T) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3396kb
input:
4 2 1 2 5 4 6 5 8
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 2ms
memory: 3464kb
input:
3 1 4 2 3 7 4
output:
No
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 29ms
memory: 15692kb
input:
271757 150678576 28436211 82026915 150751377 329329758 207446456 449759844 245730845 425844298 93416110 220240900 414108016 268705922 158510126 362264528 715921 468258085 104286815 63874786 73971103 476243636 89261247 440888454 422989962 422041006 436065809 498263669 368104872 458751340 280953952 40...
output:
No
result:
ok answer is NO
Test #4:
score: 0
Accepted
time: 23ms
memory: 10948kb
input:
221577 208524335 361831745 22019877 116938872 278766714 208490439 171991803 306449871 80504409 482889061 476216429 301986974 27811645 339159639 66711961 161280073 484108185 49066593 138136569 482494706 410430125 227818963 2765261 373817725 460818032 441004900 291595145 154693942 282220531 451435733 ...
output:
Yes
result:
ok answer is YES
Test #5:
score: 0
Accepted
time: 22ms
memory: 10648kb
input:
212799 41673284 334039127 201672006 444779051 169499200 383117913 84865270 119237171 207319350 302778460 384230135 45018093 143617443 47731571 451430563 406615446 190672561 66458621 333885077 166304905 186434713 187384362 367887797 425198230 138019148 227104694 402709301 317130343 179837636 42849323...
output:
Yes
result:
ok answer is YES
Test #6:
score: 0
Accepted
time: 14ms
memory: 15788kb
input:
272698 495041244 486500620 114619123 65371388 409456219 155714638 179226522 481947396 250269751 302940447 106379136 141063640 347472286 319233359 5678717 269094802 101216128 312654688 411897856 348645953 253283541 392464986 230708806 292286635 451191068 294748474 261562792 110501153 259721540 143685...
output:
No
result:
ok answer is NO
Test #7:
score: 0
Accepted
time: 17ms
memory: 15484kb
input:
263670 358200835 25003166 261102104 306366055 322214885 51709988 74975948 311140029 246563050 468334364 133285403 366597058 435072224 303052252 419837169 84163989 181426478 11160045 18709777 162079182 227215684 217822846 100396177 452769440 166512639 482452727 98240873 235394876 430811510 48758500 1...
output:
Yes
result:
ok answer is YES
Test #8:
score: 0
Accepted
time: 2ms
memory: 3612kb
input:
1934 453713383 418896721 137268736 260808559 392910537 92427221 365584664 215410613 352750260 255352345 468723728 367807854 19368840 334863954 22461138 254760573 277737015 419954125 431642872 302913082 421118393 242390602 166871681 84992748 66076929 336745577 31837426 372260751 455408641 483861979 2...
output:
Yes
result:
ok answer is YES
Test #9:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
1802 289640805 313722125 15494032 21889971 68694513 105309105 19848576 172571977 315845369 338419926 149884697 51816690 208817766 338563653 408411201 96525142 377418687 47198158 422367776 78639147 420038647 371479249 55267401 280390977 227528911 61902218 175077855 81256597 41509852 160235086 2571347...
output:
No
result:
ok answer is NO
Test #10:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
1439 80782137 238034291 142599844 417101959 264333931 442814389 117287383 297228361 469040218 401303636 119935749 397965885 142344617 342276116 282616030 495475817 185151289 305798841 224790299 30443734 459921931 257614453 416452713 29523112 452224870 298833327 387155644 25147720 268492397 25858217 ...
output:
No
result:
ok answer is NO
Test #11:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
1940 475962005 285765960 34547710 33692981 416121928 342899063 126192586 34859960 391366446 294843208 134881404 329730122 244920931 337185467 233628437 254352416 252885047 128072081 95124236 436350266 250067823 376927620 277070548 168228153 96130396 297142902 227412442 135332458 379644304 309468720 ...
output:
Yes
result:
ok answer is YES
Test #12:
score: 0
Accepted
time: 2ms
memory: 3576kb
input:
1666 477192932 331967048 277918304 461642890 251368667 397547852 103700878 248968755 159095281 312089149 469274963 25901475 56746646 265500932 358425529 84318517 484867127 127805428 88700073 88758440 14077032 273878655 288036657 448249267 23901370 192501075 433772364 265530956 191082969 20027711 466...
output:
Yes
result:
ok answer is YES