Pagini recente » Cod sursa (job #1630749) | Profil Sagunistu | Cod sursa (job #885784) | Cod sursa (job #1004877) | Cod sursa (job #1976546)
#include<cstdio>
#include<vector>
#include<algorithm>
#define X first
#define Y second.first
#define Z second.second
using namespace std;
FILE * fin = fopen("cutii.in","r");
FILE * fout = fopen("cutii.out","w");
int n, T, sol;
int aib[3505][3505];
pair< int, pair<int,int> > v[3505];
//vector< pair< int, pair<int,int> > > updates;
void upd( int i, int j, int x ){
for( ; i <= n; i += ( i & (-i) ) )
for( ; j <= n; j += ( j & (-j) ) )
aib[i][j] = max( aib[i][j], x );
return;
}
int query( int i, int j ){
int maxim = 0;
for( ; i >= 1; i -= ( i & (-i) ) )
for( ; j >= 1; j -= ( j & (-j) ) )
maxim = max( aib[i][j], maxim );
return maxim;
}
void reset( int i, int j ){
for( ; i <= n; i += ( i & (-i) ) )
for( ; j <= n; j += ( j & (-j) ) )
aib[i][j] = 0;
return;
}
int main(){
fscanf( fin, "%d%d", &n, &T );
for( int t = 1; t <= T; t++ ){
for( int i = 1; i <= n; i++ ){
fscanf( fin, "%d%d%d", &v[i].X, &v[i].Y, &v[i].Z );
}
sort( v + 1, v + n + 1 );
sol = 0;
for( int i = 1; i <= n; i++ ){
int val = query( v[i].Y - 1, v[i].Z - 1 ) + 1;
upd( v[i].Y, v[i].Z, val );
sol = max( sol, val );
}
for( int i = 1; i <= n; i++ ){
reset( v[i].Y, v[i].Z );
}
fprintf( fout, "%d\n", sol );
}
return 0;
}