Solução por Frederico Bulhoes
Essa é uma aplicação do algoritmo de contagem de inversões. Ou seja ele quer saber para cada flecha quantas flechas antes estão com distância menor.
Com cuidado para não esquecer o long long podemos implementar esse algoritmo de duas formas: com merge sort ou BIT.
A solução abaixo usa Merge Sort.
Código para melhor entendimento.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| typedef long long ll; | |
| typedef vector<ll> vll; | |
| const ll inf = 0x3fffffffffffffff; | |
| ll merge(vll & v) | |
| { | |
| if (v.size() == 1) return 0; | |
| int sz = (int)v.size(); | |
| vll a; | |
| vll b; | |
| for (int i = 0; i < sz/2; i++) a.push_back(v[i]); | |
| for (int i = sz/2 ; i < sz; i++) b.push_back(v[i]); | |
| ll an = merge(a); | |
| an += merge(b); | |
| a.push_back(-inf); | |
| b.push_back(-inf); | |
| int i = 0, j = 0; | |
| for (int ind = 0; ind < sz; ind++) { | |
| if (a[i] <= b[j]) { | |
| v[ind] = b[j]; | |
| j++; | |
| an += (ll)a.size() - (ll)i - 1; | |
| } else if (a[i] > b[j]) { | |
| v[ind] = a[i]; | |
| i++; | |
| } | |
| } | |
| return an; | |
| } | |
| int main() | |
| { | |
| int n; | |
| cin >> n; | |
| vll v; | |
| ll a, b; | |
| for (int i = 0; i < n; i++) { | |
| cin >> a >> b; | |
| v.push_back(a*a + b*b); | |
| } | |
| ll resp = merge(v); | |
| cout << resp << "\n"; | |
| return 0; | |
| } |
Solução com BIT
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //solucao de Leonardo Paes | |
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define MAXN 600100 | |
| #define PB push_back | |
| typedef long long ll; | |
| int tree[MAXN], vet[MAXN], n; | |
| vector< pair< ll , ll> > m; | |
| int sum(int x){ | |
| int s=0; | |
| while(x>0){ | |
| s+=tree[x]; | |
| x-=(x&-x); | |
| } | |
| return s; | |
| } | |
| void update(int x, int k){ | |
| while(x<=n){ | |
| tree[x]+=k; | |
| x+=(x&-x); | |
| } | |
| } | |
| bool compara(pair<long long, long long> a, pair<long long ,long long> b){ | |
| return a.first < b.first; | |
| } | |
| bool compara2(pair<long long,long long> a, pair<long long ,long long> b){ | |
| return a.second < b.second; | |
| } | |
| int main(){ | |
| ios_base::sync_with_stdio(false);cin.tie(NULL); | |
| long long resp=0; | |
| cin >> n; | |
| for(int i=1; i<=n; i++){ | |
| long long a, b; | |
| cin >> a >> b; | |
| m.PB(make_pair(a*a + b*b, i)); | |
| } | |
| sort(m.begin(), m.end(), compara); | |
| int k=1; | |
| for(int i=0; i<n; i++){ | |
| if(m[i].first==m[i+1].first){ | |
| m[i].first = k; | |
| } | |
| else{ | |
| m[i].first = k; | |
| k++; | |
| } | |
| } | |
| sort(m.begin(), m.end(), compara2); | |
| for(int i=0; i<n; i++){ | |
| resp+= sum(m[i].first); | |
| update(m[i].first,1); | |
| } | |
| cout << resp << endl; | |
| return 0; | |
| } |