Submission #1251607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251607		8e7	Triple Peaks (IOI25_triples)	C++20	70 / 100	213 ms	17584 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(); 
    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]);
    };
    //first case: max at left or right
    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]); 
            }
        }
    }
    //case 2: max is in the middle, right and left are corresponding
    ll count2 = 0; 
    for (int i = 0;i < n;i++) {
        if (i - h[i] >= 0) {
            int j = i - h[i];
            if (h[j] > h[i]) {
                int k = j - (h[j] - h[i]);
                count2 += (k >= 0 && h[k] == h[j] - h[i] && h[i] != h[k]);
            }
        }
    }
    //case 3: max is in middle, right and left swap
    ll count3 = 0;
    vector<vector<int>> sets(2 * n);
    auto calc_intersection = [&] (int i, int j) {
        int indi = 0, indj = 0;
        int res = 0;
        while (indi < sets[i].size() && indj < sets[j].size()) {
            if (sets[i][indi] < sets[j][indj]) indi++;
            else if (sets[i][indi] > sets[j][indj]) indj++;
            else {
                res++;
                indi++, indj++;
            }
        }
        return res;
    };
    for (int i = 0;i < n;i++) {
        int set_ind = i + h[i];
        int set_value = i - h[i];
        //query
        int qs = i - h[i];
        debug(i, set_ind, qs);
        if (qs >= 0) {
            count3 += calc_intersection(set_ind, qs);
        }
        sets[set_ind].push_back(set_value);
    }
    debug(count1, count2, count3);
    return count1 + count2 + count3;
}

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

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