关注
这个缩进看得我难受,自己对着写了遍,测试样例都没过,楼主看看哪里错了。 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
相关推荐
查看11道真题和解析 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 你的实习产出是真实的还是包装的? #
62739次浏览 536人参与
# 第一份工作应该选择高薪还是大平台 #
220324次浏览 1035人参与
# 华泰星战营,提前锁定校招offer #
1046次浏览 177人参与
# 小红书求职进展汇总 #
238343次浏览 1397人参与
# 校招第一份工作你干了多久? #
149991次浏览 630人参与
# 大疆求职进展汇总 #
699633次浏览 4351人参与
# 商战,最累的是我们 #
31552次浏览 98人参与
# AI时代还有必要刷leetcode吗? #
47480次浏览 562人参与
# 考公VS就业,你怎么选? #
99784次浏览 521人参与
# 想从事Agent应该学习哪些技术? #
13804次浏览 385人参与
# 大学生该如何认清当下的就业环境? #
165849次浏览 907人参与
# 字节7000实习来了,你投了吗? #
43136次浏览 330人参与
# 海康威视求职进展 #
134549次浏览 555人参与
# 26届春招投递记录 #
4819次浏览 49人参与
# HR面都在聊什么? #
21333次浏览 236人参与
# 有哪些公司在面试时考察AICoding? #
26950次浏览 435人参与
# 校招生月薪1W算什么水平 #
144000次浏览 495人参与
# 毕业论文进行时 #
36354次浏览 172人参与
# 第一份工作应该选高薪还是热爱? #
172417次浏览 1075人参与
# 联影求职进展汇总 #
177023次浏览 848人参与
# 从投递到OC,你用了多久 #
36525次浏览 375人参与