main.cpp (1870B)
1 #include <iostream> 2 #include <vector> 3 #include <unordered_set> 4 #include <unordered_map> 5 #include <algorithm> 6 #include <queue> 7 8 #define ll long long 9 10 using namespace std; 11 12 13 // - idea: 14 // - compute all pairs 15 // - compute the sums and then creates sets of matches where we encode this as a list of indexes that start these triads 16 // - we can then perform some basic match to compute intersections and such within groups 17 // - is this too costly? assume there's a case where ~200_000 sums match, we then do a o(n^2) op to compare them all 18 // - on insertions we could add the number of additional matches we get to some sum 19 // - that seems better. 20 // - so when inserting the first element we add none 21 // - when inserting the second element we add 1 iff they are disjoint 22 // - we then proceed as such. 23 24 int main() { 25 26 int testCases, n, cn; 27 cin >> testCases; 28 29 for(int z = 0; z < testCases; ++z) { 30 cin >> n; 31 vector<int> ls (n,0); 32 33 for(int i = 0; i < n; ++i) { 34 cin >> cn; 35 ls[i] = cn; 36 } 37 38 long long res = 0; 39 40 unordered_map<int, unordered_set<int>> triadScores {}; 41 42 for(int i = 0; i < n-4; ++i) { 43 int score = (ls[i] + ls[i+2]) - ls[i+4]; 44 if(!triadScores.contains(score)) { 45 unordered_set<int> current {}; 46 current.insert(i); 47 triadScores[score] = current; 48 } else { 49 50 int count = triadScores[score].size(); 51 triadScores[score].insert(i); 52 if(triadScores[score].contains(i-2)) { 53 count -= 1; 54 } 55 56 if(triadScores[score].contains(i-4)) { 57 count -= 1; 58 } 59 res += count; 60 } 61 } 62 63 cout << res << endl; 64 65 } 66 }