QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#105385#5500. BarsTime7#WA 258ms3392kbC++172.5kb2023-05-13 23:43:482023-05-13 23:43:49

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-13 23:43:49]
  • 评测
  • 测评结果:WA
  • 用时:258ms
  • 内存:3392kb
  • [2023-05-13 23:43:48]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;
using lint = int64_t;

using num = int64_t;
struct frac {
    num n, d;
    frac() : n(0), d(1) { }
    frac(num _n, num _d = 1) : n(_n), d(_d) {
        num g = gcd(n, d); n /= g, d /= g;
        if(d < 0) n *= -1, d *= -1;
        assert(d != 0);
    }
    friend bool operator<(const frac &l, const frac &r) {
        return __int128(1) * l.n * r.d < __int128(1) * r.n * l.d;
    }
    friend frac operator+(const frac &l, const frac &r) {
        num g = gcd(l.d, r.d);
        return frac(r.d / g * l.n + l.d / g * r.n, l.d/g * r.d);
    }
};

struct Line {
    mutable lint k, m, c;
    mutable frac p;
    bool operator<(const Line &o) const {return k < o.k; }
    bool operator<(frac x) const {return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
    static const lint inf = LLONG_MAX;
    frac div(lint a, lint b) {
        return frac(a, b);
    }
    bool isect(iterator x, iterator y) {
        if(y == end()) { x->p = frac(inf, 1); return false;}
        if(x->k == y->k) x->p = x->m > y->m ? frac(inf, 1) : frac(-inf, 1);
        else x->p = div(y->m - x->m, x->k - y->k);
        return !(x->p < y->p);
    }
    void add(lint k, lint m, lint c) {
        auto z = insert({k, m, c, frac(0, 1)}), y = z++, x = y;
        while(isect(y, z)) z = erase(z);
        if(x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while((y = x) != begin() && !((--x)->p < y->p) )
            isect(x, erase(y));
    }
    lint query(lint x, lint y) {
        assert(!empty());
        auto l = *lower_bound(frac(x, y));
        cout<<l.k<<" "<<l.m<<" "<<l.c<<"\n";
        return l.k * x + l.m * y + l.c;
    }
};




int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        vector<lint>p(n+2);
        for(int i=1;i<=n;i++) cin>>p[i];
        vector<int>left(1), right(1, n+1);

        for(int i=1;i<=n;i++){
            if(p[i] > p[left.back()]) left.push_back(i);
        }
        for(int i=n;i>=1;i--){
            if(p[i] > p[right.back()]) right.push_back(i);
        }
        reverse(right.begin(), right.end());
        for(int u : right) left.push_back(u);
        int m = int(size(left));
        lint ans = 0;
        for(int i=1;i<m;i++){
            ans += (left[i] - left[i-1]) * (p[left[i]] + p[left[i-1]]); 
        }
        ans -= p[left[1]] + p[left[m-2]];
        cout<<ans<<"\n";
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3368kb

input:

2
4
5 2 2 6
5
1 5 4 4 1

output:

33
29

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 258ms
memory: 3392kb

input:

10000
4
5 2 2 6
5
1 5 4 4 1
197
763787596 15221694 898228999 187472305 466351873 822742732 437754202 800092772 843092246 915675776 166265020 346340615 796714085 497548541 182089610 64356048 363276768 181268733 257949015 236568898 752096761 928725929 443146784 114577469 833053207 38120723 14891030 41...

output:

33
29
381268324603
658930892444
543073796232
458946673513
296420749955
872966641760
630432425409
583595848800
225238172692
715347519911
462034667948
273545943459
585094154153
200443831314
336548821022
483213442818
602558460217
586771956643
400264139273
826365121407
975377092201
920978353624
26408806...

result:

wrong answer 3rd lines differ - expected: '382465638565', found: '381268324603'