Cod sursa(job #1976546)

Utilizator robx12lnLinca Robert robx12ln Data 3 mai 2017 17:39:26
Problema Cutii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#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;
}