Cod sursa(job #2061852)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 9 noiembrie 2017 19:25:06
Problema Numarare triunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <iostream>
#include <fstream>
#include <set>
#include <algorithm>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

using namespace std;
ifstream in("nrtri.in");
ofstream out("nrtri.out");

using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
#define pb push_back
#define mp make_pair
const int NMax = 5e6 + 5;
const ll inf = 1e18 + 5;
const int mod = 100003;
using zint = int;

int N,K;
int v[NMax];

int main() {
    in>>N;
    for (int i=1;i <= N;++i) {
        in>>v[i];
    }

    // se sorteaza crescator;
    sort(v+1,v+N+1);

    int ans = 0;
    // se cauta toate trei perechile distincte care indeplinesc inegalitatea triunghiului;
    for (int i=1;i <= N-2;++i) {
        for (int j=i+1;j <= N-1;++j) {
            // avand doua betisoare fixate, se cauta al treilea prin cautarea binara;
            // ne intereseaza cel mai mare index pos de la dreapta lui j astfel incat
            // v[pos] nu depaseste v[i] + v[j];
            // astfel, v[i] + v[j] <= v[pos],
            // iar celelalte inegalitati rezulta din faptul ca vectorul e sortat crescator;

            int pos = j, pw = 1;
            while (pw <= N) {
                pw <<= 1;
            }
            pw >>= 1;

            while (pw) {
                if (pos+pw <= N && v[pos+pw] <= v[i] + v[j]) {
                    pos += pw;
                }

                pw >>= 1;
            }

            ans += pos-j;
        }
    }

    out<<ans<<'\n';

    in.close();out.close();
    return 0;
}