关注
这个缩进看得我难受,自己对着写了遍,测试样例都没过,楼主看看哪里错了。 typedef long long LL; int main() { int n; cin >> n; if (n <= 1) { cout << 0 << endl; return 0; } vector<LL> a(n); for (int i = 0; i < n; i++) cin >> a[i]; stack<pair<LL, int> > s; vector<int> c(n), d(n); for (int i = 0; i < n; i++) { while (!s.empty() && s.top().first > a[i]) s.pop(); if (s.empty()) c[i] = -1; else c[i] = s.top().second; s.push(make_pair(a[i], i)); } s = stack<pair<LL, int> >(); for (int i = n - 1; i >= 0; i--) { while (!s.empty() && s.top().first >= a[i]) s.pop(); if (s.empty()) d[i] = n; else d[i] = s.top().second; s.push({ a[i], i }); } LL res = 0; for (int i = 0; i < n; i++) { res -= a[i] * (i - c[i]) * (d[i] - i); } s = stack<pair<LL, int> >(); for (int i = 0; i < n; i++) { while (!s.empty() && s.top().first <= a[i]) s.pop(); if (s.empty()) c[i] = -1; else c[i] = s.top().second; s.push({ a[i], i }); } s = stack<pair<LL, int> >(); for (int i = n - 1; i >= 0; i--) { while (!s.empty() && s.top().first < a[i]) s.pop(); if (s.empty()) d[i] = n; else d[i] = s.top().second; s.push({ a[i], i }); } for (int i = 0; i < n; i++) { res += a[i] * (i - c[i]) * (d[i] - 1); } cout << res << endl; return 0; }
查看原帖
点赞 2
相关推荐
牛客热帖
正在热议
# 25届秋招公司红黑榜 #
126761次浏览 624人参与
# 非技术投递记录 #
441048次浏览 5549人参与
# 不考虑薪资和职业,你最想做什么工作呢? #
24385次浏览 209人参与
# Offer比较,求稳定还是求发展 #
23106次浏览 162人参与
# 如果再来一次,你还会选择这个工作吗? #
26862次浏览 421人参与
# 25届秋招总结 #
65477次浏览 717人参与
# Offer比较,你最看重什么? #
100909次浏览 744人参与
# 诺瓦星云求职进展汇总 #
150654次浏览 1482人参与
# 通信硬件人笔面经互助 #
1032307次浏览 14787人参与
# 我的实习求职记录 #
5859041次浏览 82052人参与
# 研究所VS国企,该如何选 #
116029次浏览 1418人参与
# 秋招盘点:机械人值得去的企业 #
41745次浏览 564人参与
# 我的实习日记 #
1283188次浏览 15934人参与
# 投格力的你,拿到offer了吗? #
40170次浏览 304人参与
# 你已经投递多少份简历了 #
600359次浏览 7259人参与
# 机械制造笔面经 #
1863556次浏览 28952人参与
# 选择和努力,哪个更重要? #
18057次浏览 156人参与
# 今年秋招哪家公司给的薪资最良心? #
26362次浏览 209人参与
# 你还有多少年退休? #
6963次浏览 61人参与
# 大疆求职进展汇总 #
378132次浏览 2764人参与