Pagini recente » Diferente pentru utilizator/clelia intre reviziile 12 si 13 | Cod sursa (job #408992) | Borderou de evaluare (job #1596723) | Cod sursa (job #1655986)
#include <fstream>
#include <math.h>
#define NMAX 4000
#include <algorithm>
using namespace std;
FILE *fin=fopen("cutii.in","r");
FILE *fout=fopen("cutii.out","w");
int n,t,m[NMAX][NMAX];
struct cutie
{
int x,y,z;
} v[NMAX];
int maxi(int a,int b)
{
if(a>b)
return a;
return b;
}
void update1(int val, int x,int y)
{
for(int i=x;i<=n;i+=i&(-i))
for(int j=y;j<=n;j+=j&(-j))
m[i][j]=maxi(m[i][j],val);
}
void xsort()
{
int k=10,p=1;
int m[10][NMAX];
int c;
cutie v2[NMAX];
int maxim=0;
int curent;
for(int i=1; i<=n; i++)
{
curent = log10(v[i].z)+1;
if(maxim<curent)
maxim=curent;
}
while(maxim)
{
for(int i=0; i<10; i++)
m[i][0]=0;
for(int i=1; i<=n; i++)
{
c=(v[i].z%k)/p;
m[c][0]++;
m[c][m[c][0]]=i;
}
int contor=1;
for(int i=0; i<10; i++)
for(int j=1; j<=m[i][j]; j++)
v2[contor++]=v[m[i][j]];
for(int i=1; i<=n; i++)
{
v[i]=v2[i];
}
maxim--;
}
}
bool sortez(cutie a, cutie b) {
if (a.x == b.x) {
if (a.y == b.y) {
return a.z < b.z;
}
return a.y < b.y;
}
return a.x < b.x;
};
int querry1(int x,int y)
{
int ans=0;
for(int i=x;i>0;i-=i&(-i))
for(int j=y;j>0;j-=j&(-j))
ans=maxi(m[i][j],ans);
return ans;
}
void set0(int val,int x,int y)
{
for(int i=x;i<=n;i+=i&(-i))
for(int j=y;j<=n;j+=j&(-j))
m[i][j]=0;
}
int main()
{
int k1,k2,i;
fscanf(fin,"%d%d",&n,&t);
for(k1=1; k1<=t; k1++)
{
for(k2=1; k2<=n; k2++)
fscanf(fin,"%d%d%d",&v[k2].x,&v[k2].y,&v[k2].z);
sort(v + 1, v + n + 1, sortez);
for(i=1; i<=n; i++)
update1(querry1(v[i].x-1,v[i].y-1)+1,v[i].x,v[i].y);
fprintf(fout,"%d\n",querry1(n,n));
for(i=1; i<=n; i++)
set0(0,v[i].x,v[i].y);
}
return 0;
}