关注
这个缩进看得我难受,自己对着写了遍,测试样例都没过,楼主看看哪里错了。 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
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
07-11 12:00
北京航空航天大学 Web前端 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 技术岗笔试题求解 #
77680次浏览 1005人参与
# 拼多多求职进展汇总 #
642399次浏览 4984人参与
# 工作一周年分享 #
30732次浏览 180人参与
# 如果公司给你放一天假,你会怎么度过? #
16301次浏览 122人参与
# 作业帮求职进展汇总 #
55787次浏览 370人参与
# 华子oc时间线 #
1236457次浏览 6473人参与
# OPPO求职进展汇总 #
662228次浏览 5034人参与
# 总结:哪家公司面试体验感最差 #
60508次浏览 273人参与
# 职场上哪些事情令人讨厌 #
18757次浏览 91人参与
# 三一重工求职进展汇总 #
14365次浏览 65人参与
# 去年你投递实习了吗? #
22019次浏览 329人参与
# 这些公司卡简历很严格 #
41315次浏览 204人参与
# 扒一扒那些奇葩实习经历 #
66337次浏览 913人参与
# 经纬恒润求职进展汇总 #
121698次浏览 1032人参与
# 提前批过来人的忠告 #
113910次浏览 1194人参与
# 说说你知道的学历厂 #
58833次浏览 352人参与
# 秋招最大的收获是什么? #
36913次浏览 311人参与
# 找工作时的取与舍 #
80047次浏览 566人参与
# 你认为小厂实习有用吗? #
29528次浏览 341人参与
# 哪一瞬间觉得自己长大了 #
14019次浏览 327人参与