Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- const long long N = 2e5 + 5;
- unordered_map < long long , long long > tree[4 * N];
- long long cnt = 0;
- long long n;
- long long k;
- long long a[N];
- long long maxi(long long a , long long b){
- if(a < b){
- return b;
- }
- else{
- return a;
- }
- }
- unordered_map < long long , long long > Merge(unordered_map < long long , long long > A , unordered_map < long long , long long > B){
- unordered_map < long long , long long > res;
- for(auto j : A){
- res[(j).first] += (j).second;
- }
- for(auto j : B){
- res[(j).first] += (j).second;
- }
- return res;
- }
- void build(long long node , long long s , long long e){
- if(s == e){
- tree[node][a[s]]++;
- return ;
- }
- long long mid = (s + e) / 2;
- // cout << "dsjdj" << endl;
- build(node * 2 + 1 , s , mid);
- build(node * 2 + 2 , mid + 1 , e);
- tree[node] = Merge(tree[2 * node + 1] , tree[2 * node + 2]);
- return ;
- }
- long long query(long long node , long long s , long long e , long long l , long long r , long long val){
- if(e < l || s > r){
- return 0;
- }
- if(l <= s && r >= e){
- return tree[node][val];
- }
- long long mid = (s + e) / 2;
- return query(node * 2 + 1 , s , mid , l , r , val) + query(node * 2 + 2 , mid + 1 , e , l , r , val);
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- cin >> n >> k;
- for(long long i = 0 ; i < n ; i++){
- cin >> a[i];
- }
- build(0 , 0 , n - 1);
- for(long long i = 1 ; i < n - 1 ; i++){
- if(k != 1){
- if(a[i] % k == 0){
- long long fi = query(0 , 0 , n - 1 , 0 , i - 1 , a[i] / k);
- long long se = query(0 , 0 , n - 1 , i + 1 , n - 1 , a[i] * k);
- // cout << fi << " " << se << endl;
- cnt += fi * se;
- }
- }
- else{
- long long fi = query(0 , 0 , n - 1 , 0 , i - 1 , a[i]);
- long long se = query(0 , 0 , n - 1 , i + 1 , n - 1 , a[i]);
- cnt += fi * se;
- }
- }
- cout << cnt << endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment