제출 #1251583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251583		8e7	Triple Peaks (IOI25_triples)	C++20	11 / 100	20 ms	1864 KiB

triples

//Challenge: Accepted
#include "triples.h"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif

#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
#define iter(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
#define pb emplace_back

long long count_triples(std::vector<int> h) {
    int n = h.size(); 
    //first case: max at left or right
    //
    auto check_triple = [&] (int i, int j, int k) {
        if (i < 0 || i >= n || j < 0 || j >= n || k < 0 || k >= n) return false;
        int a[3] = {abs(j - i), abs(k - j), abs(k - i)};
        int b[3] = {h[i], h[j], h[k]};
        sort(a, a + 3);
        sort(b, b + 3);
        return (a[0] == b[0]) && (a[1] == b[1]) && (a[2] == b[2]);
    };
    ll count1 = 0;
    for (int i = 0;i < n;i++) {
        if (i + h[i] < n) {
            int j = i+h[i];
            if (h[j] < h[i]) {
                count1 += check_triple(i, j, j - h[j]);
                if (j - h[j] != i + h[j]) count1 += check_triple(i, j, i + h[j]); 
            }
        }
        if (i - h[i] >= 0) {
            int j = i - h[i];
            if (h[j] < h[i]) {
                count1 += check_triple(i, j, j + h[j]); 
                if (j + h[j] != i - h[j]) count1 += check_triple(i, j, i - h[j]); 
            }
        }
    }
    return count1;
}

std::vector<int> construct_range(int M, int K) {
  return {1, 1, 1};
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 8
• Subtask 2: 0 / 6
• Subtask 3: 0 / 10
• Subtask 4: 11 / 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