QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#118903#1914. Falling Portalsbashkort#7.142857 227ms34528kbC++204.1kb2023-07-04 15:21:422024-05-31 18:59:17

Judging History

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

  • [2024-05-31 18:59:17]
  • 评测
  • 测评结果:7.142857
  • 用时:227ms
  • 内存:34528kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-04 15:21:42]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using db = long double;

struct Frac {
    ll a = 1e9, b = 1;
    Frac() = default;
    Frac(ll a, ll b) : a(a), b(b) {}
    bool operator<(const Frac &oth) const { return a * oth.b < b * oth.a; }
    bool operator>(const Frac &oth) const { return a * oth.b > b * oth.a; }
    bool operator==(const Frac &oth) const { return a * oth.b == b * oth.a; }
};

struct Line {
    ll k = 0, b = -1e18;
    Line() = default;
    Line(ll k, ll b) : k(k), b(b) {}
    db inter(const Line &oth) const { return (b - oth.b) / db(oth.k - k); }
    Frac f(ll h, int i) const {
        if (k == i) {
            assert(h == -b);
            return {0, 1};
        }
        assert(k > i);
        assert(-b >= h);
        return Frac((-b - h), k - i);
    }
};

struct CHT {
    vector<Line> t;

    void insert(const Line &v) {
        assert(t.empty() || t.back().k > v.k);
        while (size(t) > 1 && v.inter(t.end()[-2]) < v.inter(t.back())) {
            t.pop_back();
        }
        t.push_back(v);
    }

    Frac query(ll h, int i) {
        if (t.empty()) {
            return {};
        }
        int lo = 0, hi = size(t) - 1;
        while (lo < hi) {
            int mid = lo + hi >> 1;
            if (t[mid].f(h, i) > t[mid + 1].f(h, i)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return t[lo].f(h, i);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> h(n), Q(n);

    for (int i = 0; i < n; ++i) {
        cin >> h[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> Q[i];
        --Q[i];
    }

    vector<Frac> answers(n);

    auto solve = [&]() -> vector<Frac> {
        const int sz = 1 << __lg(n) + !!(n & (n - 1));
        vector<CHT> tree(sz << 1);

        vector<int> ord(n), inv(n), head(n);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int i, int j) {
            return h[i] < h[j];
        });

        for (int i = 0, j = 0; i < n; i = j) {
            while (j < n && h[ord[i]] == h[ord[j]]) {
                j += 1;
            }
            int f = i;
            while (i < j) {
                inv[ord[i]] = i;
                head[ord[i]] = f;
                i += 1;
            }
        }

        vector<vector<int>> queries(n);

        for (int s = 0; s < n; ++s) {
            int t = Q[s];
            if (h[t] <= h[s]) {
                queries[max(s, t)].push_back(s);
            }
        }

        auto ins = [&](const Line &v, int i) {
            for (int x = i + sz; x > 0; x >>= 1) {
                tree[x].insert(v);
            }
        };

        auto que = [&](int l, int r, ll h, int t)-> Frac {
            Frac ans{};
            for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
                if (l & 1) {
                    ans = min(ans, tree[l++].query(h, t));
                }
                if (r & 1) {
                    ans = min(ans, tree[--r].query(h, t));
                }
            }
            return ans;
        };

        vector<Frac> ans(n);

        for (int i = n - 1; i >= 0; --i) {
            ins({i, -h[i]}, inv[i]);
            for (int s : queries[i]) {
                int t = Q[s];
                ans[s] = que(head[s], n, h[t], t);
            }
        }

        return ans;
    };

    answers = solve();

    reverse(h.begin(), h.end());
    reverse(Q.begin(), Q.end());
    for (int i = 0; i < n; ++i) {
        h[i] = 1e9 - h[i] + 1;
        Q[i] = n - Q[i] - 1;
    }

    auto sec = solve();
    reverse(sec.begin(), sec.end());

    for (int i = 0; i < n; ++i) {
        answers[i] = min(answers[i], sec[i]);
    }

    for (int s = 0; s < n; ++s) {
        Frac ans = answers[s];
        ll d = gcd(ans.a, ans.b);
        ans.a /= d, ans.b /= d;
        if (ans < Frac(1e9, 1)) {
            cout << ans.a << "/" << ans.b << '\n';
        } else {
            cout << "-1\n";
        }
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 7.14286
Accepted
time: 0ms
memory: 3804kb

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: 210ms
memory: 28280kb

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:

28899091/1912
5420750/19719
452538539/85232
82564959/16297
148851281/50439
243893772/33319
395571559/51586
50966299/35524
113151928/14773
85286403/21085
40893683/442
128612227/16712
38223230/23039
20119164/2731
569084491/8090
270852785/68242
57756161/5520
26637397/542
584540705/11904
586005511/1221
...

result:

wrong answer 1st lines differ - expected: '118375763/30533', found: '28899091/1912'

Test #3:

score: 0
Wrong Answer
time: 190ms
memory: 28488kb

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
2523578/717
127224269/24185
319327425/95353
974493012/7847
538567300/21789
381502333/4178
772204432/46505
107346530/803
305196929/4562
269743269/65074
281696276/51043
129734587/30488
668767570/39487
13292088/11273
314313027/41899
93984043/9778
32820565/86973
67471003/62362
570052820/968...

result:

wrong answer 2nd lines differ - expected: '292813/7595', found: '2523578/717'

Test #4:

score: 0
Wrong Answer
time: 210ms
memory: 34528kb

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
33468604/86295
13665951/9628
75917/29913
140632343/20624
1618810/2273
4881596/601
49022721/6184
86104909/77634
63320953/76028
45485815/97949
3169491/47888
183980595/55382
267807/89728
35431893/4412
22031462/10927
98104714/59561
22639911/87431
8633327/169...

result:

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

Test #5:

score: 0
Wrong Answer
time: 204ms
memory: 34048kb

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
401456499/35696
52985461/6135
943959022/35441
983266117/36224
959062715/59614
147900748/33431
914265563/29024
912904867/6701
5773989/53987
931720286/6409
45711958/6765
177462577/24324
487525133/1046
916983843/8384
216526559/36312
903852108/11471
1073699/14360
224493881/42783
14157948...

result:

wrong answer 2nd lines differ - expected: '401837273/42017', found: '401456499/35696'

Test #6:

score: 0
Wrong Answer
time: 203ms
memory: 33920kb

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
147691719/578
162411978/68491
7391521/7630
880524841/423
264626224/32479
13153700/88479
793496271/26278
4457716/1137
164044531/68157
735461514/32647
223786792/42439
62467229/83037
735255136/51631
4512211/456
202494709/30804
446824399/4106
201641486/59151
8441109/1285
828592451/17134
39...

result:

wrong answer 2nd lines differ - expected: '105551441/9703', found: '147691719/578'

Test #7:

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

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
95822956/15
56687437/42
253499725/86
355485267/2
476669384/19
346569098/17
722738799/65
290144530/3
287860998/35
284359786/29
75815059/4
47435537/1
-1
87759735/2
13850123/2
767647488/31
700869797/18
497874367/28
54520241/20
282646370/1
225235887/17
282619268/5
297277579/38
34722875/24
2...

result:

wrong answer 2nd lines differ - expected: '499461693/79', found: '95822956/15'

Test #8:

score: 0
Wrong Answer
time: 0ms
memory: 3800kb

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
846168759/88
479227615/21
312966442/25
55265386/27
205613061/20
28589599/8
698757717/19
89021968/17
758547845/21
274426577/13
811758438/43
501895629/13
145892371/43
341183805/13
901192191/22
901192191/22
3449937/1
-1
382920811/32
15854062/1
402414433/20
184732892/11
-1
1024...

result:

wrong answer 4th lines differ - expected: '851541346/89', found: '846168759/88'

Test #9:

score: 0
Wrong Answer
time: 0ms
memory: 4260kb

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
64522786/789
286668687/404
71254561/58
106942807/248
424087458/967
141060098/1665
55164507/397
-1
17387893/81
137708607/1814
169110075/136
690319543/523
234038969/1165
276874481/787
733902439/425
68749291/781
461097890/629
380689957/1946
-1
52319373/137
27335721/13
641507572/521
490170...

result:

wrong answer 2nd lines differ - expected: '68924125/851', found: '64522786/789'

Test #10:

score: 0
Wrong Answer
time: 3ms
memory: 4036kb

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:

144239063/42
38621117/206
214354369/1137
386100512/27
85820547/65
62566915/251
99003005/344
358269499/550
180533378/235
14844185/572
128263937/513
522775648/961
44859828/11
175229310/299
382634689/502
270411193/231
721196575/1036
789793591/1474
66940831/480
6572429/119
110142397/776
48666785/1741
49...

result:

wrong answer 1st lines differ - expected: '103496945/1514', found: '144239063/42'

Test #11:

score: 0
Wrong Answer
time: 213ms
memory: 28320kb

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
111767909/3840
16369019/2440
84669287/13674
9871580/327
487306346/19459
69822838/4017
176270891/15211
356986812/4679
480772724/30785
497424811/31516
266683129/1806
741590725/2509
29523971/5877
592509570/84049
69622957/1387
42616123/25683
220155017/56091
26635342/10865
998388211/9832
...

result:

wrong answer 2nd lines differ - expected: '224068850/13921', found: '111767909/3840'

Test #12:

score: 0
Wrong Answer
time: 227ms
memory: 28364kb

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:

116954130/2911
118249853/13726
155263111/2414
198810525/5117
8084821/2769
334404865/19093
84266082/12443
197723502/509
157814263/21248
98433805/1858
794770271/18621
101556942/69605
82190153/13324
47223833/2157
220094888/82707
179629773/12748
329840210/883
6301327/213
671242823/75454
760481305/46688
...

result:

wrong answer 1st lines differ - expected: '78195569/6188', found: '116954130/2911'

Test #13:

score: 0
Wrong Answer
time: 210ms
memory: 28260kb

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
32912057/656
152131619/1372
251206987/9973
26291384/7555
16984427/2366
375723725/9357
90622325/10837
36115663/12304
74260045/2412
67612945/21223
963462614/9683
308404938/34405
3893485/11669
407950073/41963
445080473/8628
154809641/33303
34257277/2608
72782331/6229
595287471/26000
823...

result:

wrong answer 2nd lines differ - expected: '266183846/35305', found: '32912057/656'

Test #14:

score: 0
Wrong Answer
time: 199ms
memory: 28280kb

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:

241092506/5655
51144568/51191
349046335/85638
245959408/28035
72903083/19044
329825178/60235
813556168/80343
194132988/13949
11581046/803
4759354/8409
10644649/85083
31000153/2537
484663097/820
244582306/349
222536191/7734
42808967/47180
261453758/35367
51367878/14297
130655890/25201
55711309/673
14...

result:

wrong answer 1st lines differ - expected: '80903637/10393', found: '241092506/5655'