QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#105385 | #5500. Bars | Time7# | WA | 258ms | 3392kb | C++17 | 2.5kb | 2023-05-13 23:43:48 | 2023-05-13 23:43:49 |
Judging History
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'