QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#549014 | #1914. Falling Portals | isirazeev | 100 ✓ | 52ms | 13368kb | C++20 | 3.7kb | 2024-09-06 00:10:26 | 2024-09-06 00:10:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = (int) 1e5 * 3 + 10;
pair<int, int> get1(int a1, int i1, int a2, int i2) {
int minus = 1, d = abs(__gcd(a1 - a2, i1 - i2));
if (a1 - a2 < 0) minus = -1;
return {((a1 - a2) / d) * minus, ((i1 - i2) / d) * minus};
}
bool smaller(pair<int, int> p, pair<int, int> q) {
if (q.first == (int) 1e18) return true;
return p.first * q.second < q.first * p.second;
}
int sign(int x) {
return (x >= 0 ? 1 : -1);
}
bool good(pair<int, int> p) {
return sign(p.first) == sign(p.second);
}
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;
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]--;
for (int i = 0; i < n; i++) ans[i] = {(int) 1e18, (int) 1e18};
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 = -1, r = sz - 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (intersectX(st[mid], t) < 0) {
r = mid;
continue;
}
if (intersectX(st[mid], t) >= (mid + 1 < (int) st.size() ? intersectX(st[mid], st[mid + 1]) : -1e18))
r = mid;
else
l = mid;
}
ans[i] = intersect(st[r], 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 = -1, r = sz - 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (intersectX(st[mid], t) < 0) {
r = mid;
continue;
}
if (intersectX(st[mid], t) >= (mid + 1 < (int) st.size() ? intersectX(st[mid], st[mid + 1]) : -1e18))
r = mid;
else
l = mid;
}
ans[i] = intersect(st[r], 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: 7724kb
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: 7.14286
Accepted
time: 43ms
memory: 11996kb
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:
118375763/30533 11053819/47471 452538539/85232 82564959/16297 148851281/50439 122013689/41739 395571559/51586 50966299/35524 113950033/59505 5059268/1743 203889403/2459 128612227/16712 19285065/29918 20119164/2731 570038339/78901 270852785/68242 58081509/72133 13105812/1853 584540705/11904 586005511...
result:
ok 100000 lines
Test #3:
score: 7.14286
Accepted
time: 43ms
memory: 9968kb
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 127274533/24541 319327425/95353 974493012/7847 539101511/77671 765015070/53031 772204432/46505 107346530/803 305933147/92646 136015920/45367 281816371/60820 129734587/30488 668767570/39487 1702501/5553 314313027/41899 93984043/9778 32820565/86973 67943293/79172 570052820/968...
result:
ok 100000 lines
Test #4:
score: 7.14286
Accepted
time: 52ms
memory: 10060kb
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 32033856/10529 33468604/86295 13665951/9628 75917/29913 140632343/20624 1618810/2273 136670087/16827 49022721/6184 86104909/77634 63320953/76028 45485815/97949 3169491/47888 183980595/55382 267807/89728 47243948/5883 22031462/10927 98104714/59561 22639911/87431 8633327...
result:
ok 100000 lines
Test #5:
score: 7.14286
Accepted
time: 43ms
memory: 10228kb
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 401837273/42017 52985461/6135 943970452/35443 492996999/22981 959092712/59617 147900748/33431 458123337/33283 912916297/6703 5773989/53987 919367101/17350 45714493/6767 177462577/24324 975844263/99061 916995273/8386 216526559/36312 452664437/29626 1073699/14360 56115974/10695 2915296...
result:
ok 100000 lines
Test #6:
score: 7.14286
Accepted
time: 43ms
memory: 12436kb
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 105551441/9703 162411978/68491 7391521/7630 862086071/9778 264626224/32479 13153700/88479 396899586/14735 4457716/1137 164044531/68157 245665273/13453 37301557/7074 62467229/83037 736027274/68047 1494072/151 202494709/30804 161350385/17531 201641486/59151 8441109/1285 828813402/31795 3...
result:
ok 100000 lines
Test #7:
score: 7.14286
Accepted
time: 1ms
memory: 7724kb
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 253499725/86 354956825/18 476669384/19 353515088/23 722738799/65 142459051/37 101926695/19 284359786/29 46481471/55 47435537/1 -1 630417805/24 159135663/29 750699957/37 353261461/15 497874367/28 90739905/41 173559563/28 295815304/71 391143218/19 379371014/71 347...
result:
ok 100 lines
Test #8:
score: 7.14286
Accepted
time: 1ms
memory: 7656kb
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 534493001/48 312966442/25 55265386/27 209881306/83 6020471/3 479706304/65 172671349/33 55614671/4 274426577/13 811758438/43 501895629/13 3353383/1 671014573/36 444919577/16 444919577/16 3449937/1 -1 112990271/25 15854062/1 442582477/42 772096419/52 -1 209881306...
result:
ok 100 lines
Test #9:
score: 7.14286
Accepted
time: 0ms
memory: 7980kb
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 68924125/851 286668687/404 71254561/58 106942807/248 439394663/1060 141060098/1665 63149446/1097 -1 88636189/944 137708607/1814 342292000/1507 697909937/847 234038969/1165 240824277/728 183641868/233 37492745/708 71870617/141 380689957/1946 -1 53373135/232 49450207/85 641507572/521 490...
result:
ok 2000 lines
Test #10:
score: 7.14286
Accepted
time: 2ms
memory: 7784kb
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:
103496945/1514 38621117/206 214354369/1137 434894295/118 85820547/65 8143709/150 99003005/344 360180127/1036 361290967/619 14844185/572 128263937/513 59632543/151 329391712/1187 175253001/1957 382634689/502 299418937/275 721196575/1036 789793591/1474 67520179/1216 13238478/293 110142397/776 48666785...
result:
ok 2000 lines
Test #11:
score: 7.14286
Accepted
time: 39ms
memory: 12964kb
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 224068850/13921 8316026/43183 85696607/38097 30320918/90267 489138301/91530 628455461/44446 176270891/15211 356986812/4679 480772724/30785 250342825/16882 80194658/4259 638803425/8669 59604797/88222 592509570/84049 140551961/38322 42866799/31739 220155017/56091 26635342/10865 3091666...
result:
ok 100000 lines
Test #12:
score: 7.14286
Accepted
time: 43ms
memory: 12184kb
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:
78195569/6188 118249853/13726 933069795/55571 199478414/46539 8084821/2769 334404865/19093 84266082/12443 198110791/44946 157814263/21248 691410583/34791 794770271/18621 101556942/69605 27543934/23849 48263377/13599 220094888/82707 181953895/37718 23533574/3595 6301327/213 671242823/75454 760481305/...
result:
ok 100000 lines
Test #13:
score: 7.14286
Accepted
time: 39ms
memory: 9836kb
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 266183846/35305 458189052/69307 63386226/18055 26291384/7555 16984427/2366 375723725/9357 90622325/10837 36115663/12304 224684075/29523 67612945/21223 964201005/20009 308404938/34405 3893485/11669 407950073/41963 445080473/8628 154809641/33303 35076649/72687 218627375/39146 595287471...
result:
ok 100000 lines
Test #14:
score: 7.14286
Accepted
time: 44ms
memory: 13368kb
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:
80903637/10393 51144568/51191 349046335/85638 246275323/47150 72903083/19044 329825178/60235 813556168/80343 49429722/6665 710023811/66448 4759354/8409 10644649/85083 31000153/2537 162013881/4618 470378787/26119 111800162/39097 5352731/8508 261385409/37405 51367878/14297 130655890/25201 222852230/11...
result:
ok 100000 lines