关注
这个缩进看得我难受,自己对着写了遍,测试样例都没过,楼主看看哪里错了。 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
相关推荐
牛客热帖
更多
正在热议
更多
# 这个offer值得去吗? #
12825次浏览 141人参与
# 金三银四,你的春招进行到哪个阶段了? #
35099次浏览 329人参与
# 联宝杯大学生创新大赛,你的技术值得产业级答案 #
45870次浏览 509人参与
# 如果春招能重来,我会___ #
14407次浏览 169人参与
# 校招第一份工作你干了多久? #
152801次浏览 640人参与
# 除了线上,还能去哪些地方投简历 #
8187次浏览 93人参与
# 你觉得实习能学到东西吗 #
153139次浏览 1480人参与
# 搜狐工作体验 #
6786次浏览 54人参与
# 想做Agent可以做哪些岗位? #
12362次浏览 399人参与
# 招银网络科技(深圳)有限公司成都分公司笔试 #
6018次浏览 23人参与
# 面试官拷打AI项目都会问什么? #
11258次浏览 394人参与
# 反问环节如何提问 #
141334次浏览 2740人参与
# 你觉得最好用的AI编程工具是_ #
4394次浏览 85人参与
# 哔哩哔哩笔试 #
42279次浏览 166人参与
# 你实习是赚钱了还是亏钱了? #
127052次浏览 714人参与
# 军工所铁饭碗 vs 互联网高薪资,你会选谁 #
13962次浏览 79人参与
# 非技术岗简历怎么写 #
338586次浏览 3301人参与
# 大厂还是考编 #
134443次浏览 1398人参与
# 入职第一天,你准备什么时候下班 #
122906次浏览 525人参与
# 机械人选offer,最看重什么? #
180847次浏览 873人参与
# 大疆工作体验 #
31567次浏览 90人参与
