Cod sursa(job #2853032)

Utilizator amcbnCiobanu Andrei Mihai amcbn Data 19 februarie 2022 20:11:02
Problema Numarare triunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
/// [A][M][C][B][N] ///
#include <bits/stdc++.h>
using namespace std;
const int mod = 9973;
const int inf = 0x3f3f3f3f;
const char sp = ' ', nl = '\n';
ifstream fin("nrtri.in");
ofstream fout("nrtri.out");

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    fin >> n;
    vector<int> v(n);
    for (auto& x : v)
        fin >> x; 
    sort(v.begin(), v.end());
    int ans = 0;
    for (int i = 0; i < n - 2; ++i) {
        for (int j = i + 1; j < n - 1; ++j) {
            int st = j + 1, dr = n - 1, lb = n, ub = j;
            while (st <= dr) {
                int mid = (st + dr) / 2;
                if (v[j] - v[i] <= v[mid])
                    lb = mid, dr = mid - 1;
                else
                    st = mid + 1;
            }
            st = j + 1, dr = n - 1;
            while (st <= dr) {
                int mid = (st + dr) / 2;
                if (v[mid] <= v[i] + v[j])
                    ub = mid, st = mid + 1;
                else
                    dr = mid - 1;
            }
            ans += max(ub - lb + 1, 0);
        }
    }
    fout << ans;
}