QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#548953#1914. Falling Portalsisirazeev7.142857 54ms9684kbC++202.9kb2024-09-05 22:21:532024-09-05 22:21:53

Judging History

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

  • [2024-09-05 22:21:53]
  • 评测
  • 测评结果:7.142857
  • 用时:54ms
  • 内存:9684kb
  • [2024-09-05 22:21:53]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = (int) 1e5 * 2 + 10;

struct line {
    int k, b;

    line() : k(0), b(0) {};

    line(int _k, int _b) : k(_k), b(_b) {};
};

long double intersectX(line a, line b) {
    return (long double) (b.b - a.b) / (long double) (a.k - b.k);
}

pair<int, int> intersect(line a, line b) {
    int d = abs(__gcd((b.b - a.b), (a.k - b.k))), minus = (b.b < a.b ? -1 : 1);
    return {(b.b - a.b) / d * minus, (a.k - b.k) / d * minus};
}

int a[N], q[N], n, sz = 0;
pair<int, int> ans[N];
vector<line> st;

int sign(int x) {
    return (x >= 0 ? 1 : -1);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> q[i], q[i]--;
    vector<int> ord;
    for (int i = 0; i < n; i++) ord.emplace_back(i);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
        return a[i] < a[j];
    });
    reverse(ord.begin(), ord.end());
    for (int i: ord) {
        line k = line(-(i + 1), a[i]);
        while (sz >= 1) {
            if (k.k < st[sz - 1].k || (sz >= 2 && intersectX(st[sz - 1], k) >=
                                                  intersectX(st[sz - 1], st[sz - 2])))
                st.pop_back(), sz--;
            else break;
        }
        st.emplace_back(k), sz++;
        if (a[q[i]] < a[i]) {
            line t = line(-(q[i] + 1), a[q[i]]);
            int l = 0, r = sz;
            while (r - l > 1) {
                int mid = (l + r) / 2;
                if (intersectX(st[mid], k) >= (mid > 0 ? intersectX(st[mid], st[mid - 1]) : -1e18))
                    l = mid;
                else
                    r = mid;
            }
            ans[i] = intersect(st[l], t);
        }
    }
    st.clear(), sz = 0;
    reverse(ord.begin(), ord.end());
    for (int i: ord) {
        line k = line(-(i + 1), a[i]);
        while (sz >= 1) {
            if (k.k > st[sz - 1].k || (sz >= 2 && intersectX(st[sz - 1], k) <=
                                                  intersectX(st[sz - 1], st[sz - 2])))
                st.pop_back(), sz--;
            else break;
        }
        st.emplace_back(k), sz++;
        if (a[q[i]] > a[i]) {
            line t = line(-(q[i] + 1), a[q[i]]);
            int l = 0, r = sz;
            while (r - l > 1) {
                int mid = (l + r) / 2;
                if (intersectX(st[mid], k) <= (mid > 0 ? intersectX(st[mid], st[mid - 1]) : 1e18))
                    l = mid;
                else
                    r = mid;
            }
            ans[i] = intersect(st[l], t);
        }
    }
    for (int i = 0; i < n; i++) {
        if (ans[i].first == (int) 1e18 || sign(ans[i].first) != sign(ans[i].second)) cout << "-1\n";
        else cout << ans[i].first << "/" << ans[i].second << "\n";
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 7.14286
Accepted
time: 1ms
memory: 5596kb

input:

4
3 5 10 2
3 3 2 1

output:

7/2
7/2
5/1
-1

result:

ok 4 lines

Test #2:

score: 0
Wrong Answer
time: 50ms
memory: 9516kb

input:

100000
472909419 819415545 354941190 517113826 307239833 831177800 578834772 704837117 326642977 846249751 997452224 322958397 143787473 278464288 864820832 175161120 545824609 549197171 224617065 387719870 938593011 671365566 982006335 210657906 552581470 851423470 973444746 978545568 66820178 6528...

output:

241244953/31221
41149778/48281
452538539/85232
209334325/32597
148851281/50439
131218209/42116
62687114/6449
282893997/35531
20263629/3139
88773191/30046
203889403/2459
272943018/33431
493001077/60184
215153471/10925
44364708/6077
302226432/68245
110511785/73608
75011328/3757
221790099/3970
61878419...

result:

wrong answer 1st lines differ - expected: '118375763/30533', found: '241244953/31221'

Test #3:

score: 0
Wrong Answer
time: 51ms
memory: 9684kb

input:

100000
315623747 979206700 183094144 181505867 2572616 772718102 942741911 19472958 458398376 484546774 348949045 306690702 414701395 131437507 43708479 224826052 238532133 327518511 70279102 323433367 124141008 73101443 605805888 102782315 282343812 345273900 201043659 430908518 243739589 724275027...

output:

130531/66524
292813/7595
525151083/24941
319327425/95353
974493012/7847
710573306/77679
765015070/53031
394552387/23254
572160749/3220
200735349/46396
501841671/90841
556056596/61005
179273411/30494
797632461/39496
563884742/91191
356044935/41912
619342247/58682
44715329/86990
115649841/15859
144465...

result:

wrong answer 3rd lines differ - expected: '127274533/24541', found: '525151083/24941'

Test #4:

score: 0
Wrong Answer
time: 49ms
memory: 9544kb

input:

100000
1 4273 15397 29998 27927 48335 59992 44642 37593 89985 41136 43307 119975 48665 62351 149962 8744 116987 179946 98859 144057 209927 19516 41099 239906 183405 142896 269883 7437 83101 299858 174434 127933 329832 91448 39029 359803 174356 124036 389771 136441 166104 419738 196420 51865 449702 2...

output:

214487230/35559
88821503/17702
96116964/31589
33498601/86298
54677767/38514
276085/89744
70346167/10315
3282261/4553
68350042/8415
147158147/18561
21536511/19411
63364259/76039
45605789/97961
6387316/95781
92020293/27694
417768/89743
47243948/5883
132305758/65579
98284659/59579
22738769/87450
433106...

result:

wrong answer 3rd lines differ - expected: '32033856/10529', found: '96116964/31589'

Test #5:

score: 0
Wrong Answer
time: 49ms
memory: 9560kb

input:

100000
1 933326351 11431 29998 989129972 37227 59992 989874362 62527 89984 979798680 75881 119974 982112916 19608 149961 995611915 151806 179946 913593466 132088 209929 930585647 149041 239909 930246483 218498 269887 972955258 54548 299863 927767028 295901 329836 953302565 223592 359806 995522236 31...

output:

221281385/50982
829322777/84166
52985461/6135
943970452/35443
987715279/45986
959092712/59617
147960739/33437
183593591/13318
912916297/6703
1465993/13499
925334617/17356
45774484/6773
88791275/12168
986496071/99268
916995273/8386
216676519/36327
907112071/59273
6593999/86177
224643841/42798
2915296...

result:

wrong answer 2nd lines differ - expected: '401837273/42017', found: '829322777/84166'

Test #6:

score: 0
Wrong Answer
time: 48ms
memory: 9548kb

input:

100000
1 944663363 19033 29999 978821096 9085 59995 944910920 6257 89989 935899956 82545 119982 940520499 117973 149972 912135517 105359 179960 992861910 149037 209947 995445085 200979 239932 965159106 3211 269915 909296230 233961 299895 975484316 298245 329873 977094068 214362 359849 995636217 2225...

output:

2982983/44613
757069534/67939
54143670/22831
3857750/3981
15707617/178
264626224/32479
13213694/88485
812008619/29488
4457716/1137
164134519/68166
762978999/40438
37311556/7075
62587210/83049
379078350/34157
603628/61
202644680/30819
171427262/17537
100865737/29580
202766575/30858
75690997/2894
3910...

result:

wrong answer 2nd lines differ - expected: '105551441/9703', found: '757069534/67939'

Test #7:

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

input:

100
534473706 617535198 746655229 582822181 350704338 460330801 735571468 88013273 362424504 855094440 710187915 697682713 997401051 460972806 717634399 444280514 755460273 944591484 265200138 839544060 662809699 661469793 497227720 278087261 937000185 722532327 468846527 92827045 15385128 139854649...

output:

460073995/39
499461693/79
70579417/54
301848200/89
354956825/18
586295847/20
353515088/23
722738799/65
142459051/37
101926695/19
460073995/39
101852132/77
47435537/1
-1
630417805/24
442572991/33
750699957/37
353261461/15
497874367/28
90739905/41
173559563/28
295815304/71
54515017/2
379371014/71
2186...

result:

wrong answer 4th lines differ - expected: '253499725/86', found: '301848200/89'

Test #8:

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

input:

100
832359132 241086117 70268513 75641100 493265869 8969911 580115154 253097306 322151607 572536179 103433364 769475382 58915476 7943159 674934181 286336577 158800591 167266000 146088101 655190514 41590604 326590745 562776717 281254161 127537826 133491925 80685740 116325615 999795567 247078385 96567...

output:

-1
252179752/3
37201903/6
851541346/89
607501188/53
312966442/25
128273573/32
317502509/94
74819236/17
78959213/10
89021968/17
369132746/25
274426577/13
811758438/43
501895629/13
3353383/1
671014573/36
444919577/16
444919577/16
169084232/15
-1
64200075/14
165725031/4
442582477/42
772096419/52
-1
215...

result:

wrong answer 5th lines differ - expected: '534493001/48', found: '607501188/53'

Test #9:

score: 0
Wrong Answer
time: 2ms
memory: 7948kb

input:

2000
21505957 142018840 50835846 230286771 619214141 711966088 451418032 83312406 997278214 235672441 776998092 992475976 912444334 252212792 547270894 875994775 420249958 660039013 284835603 996966995 545404037 762620339 218177198 216536966 712712166 284586306 598975962 889965588 251816698 28540064...

output:

621739397/749
33520808/215
602667263/810
707562741/409
704650991/252
587327957/1085
570972173/1671
182030611/1121
-1
435186842/1103
446600371/912
342292000/1507
717288703/862
232372902/589
276874481/787
23472297/29
230823844/1717
856492709/1296
644019603/1964
-1
22858965/59
16684299/13
838178813/543...

result:

wrong answer 2nd lines differ - expected: '68924125/851', found: '33520808/215'

Test #10:

score: 0
Wrong Answer
time: 2ms
memory: 7756kb

input:

2000
797776435 328363264 380792931 830287509 570335429 882870824 429432401 710728673 945865610 940849228 403089500 796543599 901854446 712568094 68385691 346788092 179631402 72575296 680321593 139773675 517849401 190654156 839257552 981435241 992409916 887842045 919377993 677204575 940817503 5589288...

output:

122356085/1554
38621117/206
133392018/569
434894295/118
75415673/24
95982178/1303
596084162/1725
360180127/1036
397141904/631
157916978/581
66250822/207
555552027/1399
329391712/1187
175253001/1957
382634689/502
635406610/291
138740381/173
793983196/1477
24604043/373
104206472/217
99876178/265
85467...

result:

wrong answer 1st lines differ - expected: '103496945/1514', found: '122356085/1554'

Test #11:

score: 0
Wrong Answer
time: 42ms
memory: 9524kb

input:

100000
40496370 324535254 49378557 776806467 392153838 609799230 999070315 9268041 50237542 87633903 878656049 864388090 896320175 129811364 229732659 323726790 766611509 83562791 105404287 304944654 412773020 198917959 443657299 415124223 512809649 256079123 986186956 2116823 811457832 528369347 63...

output:

909844125/74797
430373516/14009
498253787/87383
163202103/38510
168816906/91357
606545024/91907
628939831/44474
176270891/15211
51693914/669
527910257/30794
605230669/33802
173418011/7099
242800380/2891
460509391/88506
260581953/28021
346856627/38410
131183323/31917
131610719/28054
251355311/76073
2...

result:

wrong answer 2nd lines differ - expected: '224068850/13921', found: '430373516/14009'

Test #12:

score: 0
Wrong Answer
time: 54ms
memory: 9544kb

input:

100000
747693760 346580867 964846225 969980340 332880584 194631534 209614296 522099709 464443293 921495511 83514635 841823909 900939960 262364081 256636328 411285480 427902137 406071146 24620069 112056879 943629859 862303870 308874724 251885142 471236107 744614688 681975403 212603157 214491071 32304...

output:

11915208/665
118249853/13726
943301712/55825
205382259/47299
8084821/2769
334404865/19093
133890504/18665
112710324/15191
433490952/42503
243891325/11662
794770271/18621
195687091/69616
145387495/72399
448431291/13709
141049841/41358
432007538/37793
70596851/6324
40884160/983
671242823/75454
7890235...

result:

wrong answer 1st lines differ - expected: '78195569/6188', found: '11915208/665'

Test #13:

score: 0
Wrong Answer
time: 50ms
memory: 9676kb

input:

100000
97813451 955958588 478382047 254807140 430405236 587356632 581166185 416641725 298677059 255167178 707387178 995828332 1210912 419588635 497113506 472224137 683979366 992616764 280702107 282745359 832716627 830311108 1931725 972918653 684698510 654423087 966059769 427612303 261873029 35728741...

output:

127919159/46770
280179943/35972
276507634/23291
467503688/72483
569214241/67999
829231721/47325
859076459/9363
409450599/10844
208778793/36916
438642859/29786
812412562/63679
964201005/20009
308404938/34405
345136094/70027
807250128/41977
819491159/8643
740975556/33319
38437703/72885
68125552/6621
7...

result:

wrong answer 2nd lines differ - expected: '266183846/35305', found: '280179943/35972'

Test #14:

score: 0
Wrong Answer
time: 54ms
memory: 9560kb

input:

100000
822999751 128955399 431407947 917749297 190297412 252492617 150325783 759881331 829939635 283074122 899601042 159665057 607610844 489768568 320041755 787661887 373639719 710748050 188262807 366602165 732969261 932719233 208477147 358075812 125541209 536067868 278333698 201086482 537247556 180...

output:

400217721/46846
51144568/51191
651498883/85639
178650081/31622
69049393/12697
453362396/60239
208731638/20087
217287819/26732
388325915/33272
158878077/8417
87245940/85093
867713789/68509
658159581/13907
761488589/26185
114253785/13088
155306252/68279
670755269/37911
684528407/28610
94981649/12609
6...

result:

wrong answer 1st lines differ - expected: '80903637/10393', found: '400217721/46846'