QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#183206 | #6326. Make Convex Sequence | neko_nyaa# | AC ✓ | 37ms | 9460kb | C++23 | 2.7kb | 2023-09-19 11:05:24 | 2023-09-19 11:05:25 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T x=0, T y=0) : x(x), y(y) {}
bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
P operator+(P p) const { return P(x+p.x, y+p.y); }
P operator-(P p) const { return P(x-p.x, y-p.y); }
P operator*(T d) const { return P(x*d, y*d); }
P operator/(T d) const { return P(x/d, y/d); }
T dot(P p) const { return x*p.x + y*p.y; }
T cross(P p) const { return x*p.y - y*p.x; }
T cross(P a, P b) const { return (a-*this).cross(b-*this); }
T dist2() const { return x*x + y*y; }
double dist() const { return sqrt((double)dist2()); }
// angle to x-axis in interval [-pi, pi]
double angle() const { return atan2(y, x); }
P unit() const { return *this/dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated 'a' radians ccw around the origin
P rotate(double a) const {
return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
friend ostream& operator<<(ostream& os, P p) {
return os << "(" << p.x << "," << p.y << ")"; }
};
#define int long long
bool convex(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
Point<int> A(a.first, a.second);
Point<int> B(b.first, b.second);
Point<int> C(c.first, c.second);
return A.cross(B, C) < 0;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
vector<int> l(n), r(n);
for (int &i: l) cin >> i;
for (int &i: r) cin >> i;
vector<pair<int, int>> st;
st.push_back({r[0], 0});
st.push_back({r[1], 1});
for (int i = 2; i < n; i++) {
while (st.size() >= 2) {
int sz = st.size();
if (convex(st[sz-2], st[sz-1], {r[i], i})) break;
st.pop_back();
}
st.push_back({r[i], i});
}
vector<double> rp(n);
rp[st[0].second] = st[0].first;
for (int i = 1; i < st.size(); i++) {
int lv = st[i-1].first, rv = st[i].first;
int lid = st[i-1].second, rid = st[i].second;
double cur = lv, step = 1.0*(rv-lv)/(rid-lid);
for (int j = lid; j <= rid; j++) {
rp[j] = cur; cur += step;
}
}
//for (double i: rp) cout << i << ' ';
// cout << '\n';
const double EPS = 1e-9;
for (int i = 0; i < n; i++) {
if (rp[i] < l[i]-EPS) {
cout << "No\n";
return 0;
}
}
cout << "Yes\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3540kb
input:
4 2 1 2 5 4 6 5 8
output:
Yes
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
3 1 4 2 3 7 4
output:
No
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 37ms
memory: 9380kb
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: 32ms
memory: 8332kb
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: 29ms
memory: 8064kb
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: 35ms
memory: 9460kb
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: 29ms
memory: 9380kb
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: 0ms
memory: 3888kb
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: 0ms
memory: 3584kb
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: 3664kb
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: 1ms
memory: 3604kb
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: 1ms
memory: 3552kb
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