Submission #1255133

#TimeUsernameProblemLanguageResultExecution timeMemory
1255133ro9669Triple Peaks (IOI25_triples)C++20
11 / 100
82 ms19780 KiB
#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; long long cnt[2 * maxN] , A[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 memset(cnt , 0 , sizeof(cnt)); for (int j = n - 1 ; j >= 0 ; j--){ A[j] = cnt[j + a[j]]; cnt[j + a[j]]++; } memset(cnt , 0 , sizeof(cnt)); for (int i = n - 1 ; i >= 0 ; i--){ ans += cnt[a[i] - i + maxN]; cnt[a[i] - i + maxN] += A[i]; } 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.out" , "w" , stdout); // int n; cin >> n; // vector<int> h(n); // for (int &x : h) cin >> x; // cout << count_triples(h) << "\n"; // return 0; // }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...