Hack #842 - QOJ.ac

ID	Submission ID	Problem	Hacker	Owner	Result	Submit time	Judge time
#842	#573958	#9313. Make Max	Trspnt	ZJH1214	Failed.	2024-09-18 20:37:50	2024-09-18 20:37:50

Details

Extra Test:

Accepted

time: 0ms

memory: 3872kb

input:

1
12
1 2 3 5 2 1 3 4 5 4 1 2

output:

result:

ok 1 number(s): "22"

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#573958	#9313. Make Max	ZJH1214	AC ✓	30ms	5856kb	C++20	1.0kb	2024-09-18 20:25:17	2024-09-18 20:25:18

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n + 2);
        a[0] = a[n + 1] = 2e9;
        for(int i = 1; i <= n; i++) cin >> a[i];
        LL ans = 0;
        {
            vector<int> stk{0};
            for(int i = 1; i <= n; i++){
                while(!stk.empty() and a[stk.back()] < a[i]){
                    stk.pop_back();
                }
                ans += i - stk.back() - 1;
                stk.push_back(i);
            }
        }
        {
            vector<int> stk{n + 1};
            for(int i = n; i >= 1; i--){
                while(!stk.empty() and a[stk.back()] < a[i]) stk.pop_back();
                if (a[stk.back()] != a[i]) ans += stk.back() - i - 1;
                stk.push_back(i);
            }
        }
        cout << ans << '\n';
    }

}

Source code, Language: C++20