Submission #1250633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250633		NekoRolly	Triple Peaks (IOI25_triples)	C++20	0 / 100	32 ms	2628 KiB

triples

#include "triples.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
vector<int> h;

bool same(vector<int> a,vector<int> b){
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for (int i=0; i<3; i++)
        if (a[i] != b[i]) return false;
    return true;
}

bool check(int i,int j,int k){
    return 0 <= i && i < j && j < k && k < n && same({k-i, k-j, j-i}, {h[i], h[j], h[k]});
}

ll count_triples(vector<int> H){
    h = H;
    n = h.size();

    bool not_desc = true;
    for (int i=0; i+1<n; i++)
        if (h[i] > h[i+1])
            not_desc = false;

    ll ans = 0;
    for (int i=0; i<n; i++){
        int l = i - h[i];
        int r = i + h[i];
        if (l >= 0){
            ans += check(l, l+h[l], i);
            ans += check(l, i-h[l], i);
        }
        if (r < n){
            ans += check(i, r-h[r], r);
            ans += check(i, i+h[r], r);
        }
        if (!not_desc){
            l = max(l+1, 0);
            r = min(r-1, n-1);
            for (int j=l; j+h[i]<=r; j++)
                ans += check(j, i, j+h[i]);
        }
    }

    return ans;
}

vector<int> construct_range(int M, int K){
    return {0};
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 6
• Subtask 3: 0 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 16
• Subtask 6: 0 / 19
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5