Submission #1255385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255385		ro9669	Triple Peaks (IOI25_triples)	C++20	70 / 100	139 ms	42268 KiB

triples

#include "triples.h"
#include <bits/stdc++.h>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
using namespace std;

vector<int> a;

bool ok(int i , int j , int k){
    vector<int> X = {j - i , k - j , k - i};
    vector<int> Y = {a[i] , a[j] , a[k]};
    sort(all(X)); sort(all(Y));
    bool check = true;
    for (int id = 0 ; id < 3 ; id++){
        if (X[id] != Y[id]) return false;
    }
    return true;
}

namespace sub5{
    const int maxN = int(2e5)+7;

    vector<int> pre[2 * maxN] , suf[2 * maxN];

    long long solve(){
        set<pair<int , pair<int , int>>> st;
        int n = sz(a);
        //i , j , k
        for (int i = 0 ; i < n ; i++){
            int j = i + a[i];
            if (j >= n) continue;
            int k = j + a[j];
            if (k >= n) continue;
            if (ok(i , j , k)) st.insert({i , {j , k}});
        }
        //i , k , j
        for (int i = 0 ; i < n ; i++){
            int j = i + a[i];
            if (j >= n) continue;
            int k = i + a[j];
            if (k >= n) continue;
            if (ok(i , j , k)) st.insert({i , {j , k}});
        }
        //j , i , k
        for (int j = 0 ; j < n ; j++){
            int i = j - a[j];
            if (i < 0) continue;
            int k = j + a[i];
            if (k >= n) continue;
            if (ok(i , j , k)) st.insert({i , {j , k}});
        }
        //j , k , i
        for (int j = 0 ; j < n ; j++){
            int i = j - a[j];
            if (i < 0) continue;
            int k = i + a[i];
            if (k >= n) continue;
            if (ok(i , j , k)) st.insert({i , {j , k}});
        }
        //k , j , i
        for (int i = 0 ; i < n ; i++){
            int k = i + a[i];
            if (k >= n) continue;
            int j = i + a[k];
            if (j >= n) continue;
            if (ok(i , j , k)) st.insert({i , {j , k}});
        }
        long long ans = sz(st);
        //k , i , j
        for (int k = n - 1 ; k >= 0 ; k--){
            suf[a[k] + k].push_back(k);
        }
        for (int j = 0 ; j < n ; j++){
            suf[a[j] + j].pop_back();
            if (sz(pre[a[j] - j + maxN]) < sz(suf[a[j] + j])){
                for (int i : pre[a[j] - j + maxN]){
                    int k = j + a[i];
                    if (k < n){
                        if (a[j] + j == a[k] + k) ans++;
                    }
                }
            }
            else{
                for (int k : suf[a[j] + j]){
                    int i = j - a[k];
                    if (i >= 0){
                        if (a[i] - i == a[j] - j) ans++;
                    }
                }
            }
            pre[a[j] - j + maxN].push_back(j);
        }
        for (int j = 0 ; j < n ; j++){
            if (a[j]&1) continue;
            int i = j - a[j] / 2;
            int k = j + a[j] / 2;
            if (i < 0 || k >= n) continue;
            if (ok(i , j , k)) ans--;
        }
        return ans;
    }
}

long long count_triples(vector<int> h){
    a = h;
    return sub5::solve();
}

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

// int main(){
//     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//     freopen("templete.inp" , "r" , stdin);
//     freopen("templete.ans" , "w" , stdout);
//     int n; cin >> n;
//     vector<int> h(n);
//     for (int &x : h) cin >> x;
//     cout << count_triples(h) << "\n";
//     return 0;
// }

• 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