Submission #1253299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253299		chr34	Triple Peaks (IOI25_triples)	C++20	18 / 100	2093 ms	20340 KiB

triples

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define endl "\n"
#define dbg(x) cout << #x << " = " << (x) << endl;
const long long INF = 1e18;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;

bool match(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;
}

long long count_triples(vector<int> h) {
    int n = h.size();
    long long ans = 0;

    // Preprocess: Map from height to list of indices
    unordered_map<int, vector<int>> idx_map;
    for (int i = 0; i < n; ++i)
        idx_map[h[i]].push_back(i);

    for(int i = 0; i < n; ++i){
        for(int j = i + 1; j < n; ++j){
            int di = j - i;

            if(di != h[i] && di != h[j]){ // di must be h[k], k > j
                if (idx_map.count(di)) {
                    const vector<int>& idxs = idx_map[di];
                    auto it = upper_bound(idxs.begin(), idxs.end(), j);
                    for (; it != idxs.end(); ++it) {
                        int k = *it;
                        vector<int> htriple = {h[i], h[j], h[k]};
                        vector<int> dtriple = {j - i, k - i, k - j};
                        if (match(htriple, dtriple)) ans++;
                    }
                }
            }

            else if(di == h[i]){
                int k1 = j + h[j];
                if(k1 < n && match({h[i], h[j], h[k1]}, {di, k1 - i, k1 - j})) ans++;
                int k2 = i + h[j];
                if(k2 < n && k2 > j && match({h[i], h[j], h[k2]}, {di, k2 - i, k2 - j})) ans++;
            }

            else if(di == h[j]){
                int k1 = i + h[i];
                if(k1 < n && k1 > j && match({h[i], h[j], h[k1]}, {di, k1 - i, k1 - j})) ans++;
                int k2 = j + h[i];
                if(k2 < n && match({h[i], h[j], h[k2]}, {di, k2 - i, k2 - j})) ans++;
            }
        }
    }

    return ans;
}
vector<int> construct_range(int m, int k){
	return {};
}

/*int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//freopen("input.in", "r", stdin);
	//freopen("input.out", "w", stdout);    
	cout<<count_triples({4, 1, 4, 3, 2, 6, 1});
    return 0;
}*/

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