Cod sursa(job #2379976)

Utilizator carburatorMitica Carburator carburator Data 14 martie 2019 12:13:24
Problema Triplete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("triplete.in");
ofstream fout("triplete.out");
struct elem{int un,doi;}; elem v[131075];
bool compar(elem a1, elem a2){if(a1.un>a2.un)return 0; else if(a1.un<a2.un)return 1; if(a1.doi>a2.doi)return 0; if(a1.doi<a2.doi)return 1; return 1;}
long long i,N,M,poz[4100],poz2[4100],a,b,y,j,st,dr,m,ok,nr;
int main()
{
    fin>>N>>M;
    for(i=1;i<=M;i++){ fin>>a>>b;
     v[++y].un=a; v[y].doi=b;
     v[++y].un=b; v[y].doi=a;
    }
    sort(v+1,v+y+1,compar);
//    for(i=1;i<=y;i++)fout<<v[i].un<<" "<<v[i].doi<<'\n'; fout<<'\n';

    for(i=1;i<=y;i++){
        if(!poz[v[i].un])poz[v[i].un]=i;
        poz2[v[i].un]=i;
    }
//    for(i=1;i<=4;i++)fout<<poz[i]<<" "<<poz2[i]<<'\n'; fout<<'\n';

    for(i=1;i<=y;i++){
       while(v[i].un>v[i].doi)i++;
       if(i<=y){ j=i+1;
       //verificare ptr cand prima din pereche e aceeasi
         while(v[i].un==v[j].un){
//                fout<<i<<" "<<j<<'\n';
            st=poz[v[i].doi]; dr=poz2[v[i].doi]; ok=0;
//            fout<<st<<" "<<dr<<'\n';
            while(st<=dr){ m=(st+dr)/2;
                if(v[m].doi<v[j].doi)st=m+1;
                else if(v[m].doi>v[j].doi)dr=m-1;
                else {ok=1; break;}
            }
            if(ok)nr++;
            j++;
         }
        //
       }

    }
    fout<<nr;

    return 0;
}