QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#534566#6326. Make Convex Sequenceucup-team1525#AC ✓39ms11964kbC++201.4kb2024-08-27 13:55:232024-08-27 13:55:23

Judging History

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

  • [2024-08-27 13:55:23]
  • 评测
  • 测评结果:AC
  • 用时:39ms
  • 内存:11964kb
  • [2024-08-27 13:55:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using db = long long;
const int N = 3e5 + 50;

int n;
db L[N], R[N];
using point=pair<db,db>;
point operator+(point a,point b){return {a.first+b.first,a.second+b.second};}
point operator-(point a,point b){return {a.first-b.first,a.second-b.second};}
db operator^(point a,point b){return a.first*b.second-a.second*b.first;}
using VP=vector<point>;
int dcmp(const db a){return abs(a)==0?0:(a<0?-1:1);}

VP p;

bool isonseg(point sl,point sr,point tl,point tr){
    return (dcmp((sr-tl)^(tr-tl))*dcmp((sl-tl)^(tr-tl))<=0)&&(dcmp((tr-sl)^(sr-sl))*dcmp((tl-sl)^(sr-sl))<=0);   
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n;
    p.resize(n + 5);
    for (int i =1;i<=n;i++) cin >> L[i];
    for (int i =1;i<=n;i++) cin >> R[i];
    for (int i =1;i<=n;i++)p[i]=point(i,R[i]);
    vector<int> st;
    for (int i = 1; i <= n; i++) {
        while(st.size() > 1 && dcmp((p[st.back()]-p[*(st.rbegin()+1)])^(p[i]-p[*(st.rbegin()+1)]))<=0)
            st.pop_back();
        st.push_back(i);
    }

    for (int i = 0; i+1<st.size();i++) {
        point sl=p[st[i]],sr=p[st[i+1]];
        for (int j = st[i]; j <= st[i + 1]; j++) {   
            point tl=point(j,L[j]),tr=point(j,R[j]);
            if (!isonseg(sl,sr,tl,tr)) {
                cout << "No\n";
                return 0;
            }
        }
    }
    cout << "Yes\n";
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5604kb

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: 5868kb

input:

3
1 4 2
3 7 4

output:

No

result:

ok answer is NO

Test #3:

score: 0
Accepted
time: 39ms
memory: 11964kb

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: 29ms
memory: 10708kb

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: 31ms
memory: 10096kb

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: 38ms
memory: 11856kb

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: 35ms
memory: 11680kb

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: 1ms
memory: 5748kb

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: 1ms
memory: 5656kb

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: 5592kb

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: 5712kb

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: 0ms
memory: 5712kb

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