【題解】ZeroJudge c424: pC 框架區間

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c424

#include <iostream>
#include <set>
using namespace std;

int t, n, a[5005], mx[5005], mn[5005], ans;
set <int> sts, stb;

int main() {
    cin >> t;
    while (t--){
        cin >> n;
        ans = 0;
        sts.clear();
        stb.clear();
        for (int i = 1; i <= n; i++){
            cin >> a[i];
            for (auto j:sts){
                if (a[j] < a[i]) sts.erase(j);
                else if (a[i] < mn[j]){
                    mn[j] = a[i];
                    if (a[j]-a[i] == i-j) ans++;
                }
                if (sts.empty()) break;
            }
            for (auto j:stb){
                if (a[j] > a[i]) stb.erase(j);
                else if (a[i] > mx[j]){
                    mx[j] = a[i];
                    if (a[i]-a[j] == i-j) ans++;
                }
                if (stb.empty()) break;
            }
            sts.insert(i);
            stb.insert(i);
            mn[i] = 10000;
            mx[i] = 0;
        }
        cout << ans << "\n";
    }
}
分享本文 Share with friends