Cod sursa(job #2561476)

Utilizator valentinchipuc123Valentin Chipuc valentinchipuc123 Data 28 februarie 2020 20:31:12
Problema Triplete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <algorithm>



using namespace std;

ifstream f("triplete.in");
ofstream g("triplete.out");

int n,m,poz1=1,poz2,nr;
bool mat[4100][4100];
struct relati{
 int x,y;
}v[70000];

bool cmp(relati a,relati b)
 {
  if(a.x==b.x)
    return a.y<b.y;
  return a.x<b.x;
 }
int caut(int st)
 {
  int dr=m,mid,rasp=0;
  while(st<=dr)
  {
   mid=(st+dr)/2;
   if(v[mid].x==v[st].x) {rasp=mid; st=mid+1;}
   else dr=mid-1;
  }
  return rasp;
 }
int main()
{
f>>n>>m;
for(int i=1;i<=m;i++)
 {
 f>>v[i].x>>v[i].y;
 mat[v[i].x][v[i].y]=1;
 }
sort(v+1,v+m+1,cmp);
for(int i=1;i<=m-1;i++)
 if(v[i].x==v[i+1].x&&v[i].x!=v[i-1].x)
 {
  poz1=i;
  poz2=caut(poz1);
  for(int j=poz1;j<=poz2-1;j++)
    for(int z=j+1;z<=poz2;z++)
     if(mat[j][z]==1) nr++;
 }
g<<nr;
}