Cod sursa(job #2418725)

Utilizator iandavidroIan David Bocioaca iandavidro Data 5 mai 2019 22:54:38
Problema Cutii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>
#define maxn 3500

using namespace std;

ifstream fin ( "cutii.in" );
ofstream fout ( "cutii.out" );

struct yes
{
  int x, y, z;
};

yes v[maxn+5];
int aib[maxn+5][maxn+5];///aib[i][j]=indicele celui mai mare best[ind] cu xind in (i-lsb(i),i] si yind in (j-lsb(j),j]
int best[maxn+5]; /// best[i]=subsecv de lg max care se termina in cutia i

int lsb ( int u ) { return u&(-u); }
bool cmp ( yes a, yes b ) { return a.z < b.z; }
void umax ( int &a, int b ) { a = max(a,b); }

int query ( int a, int b )
{
  int ans = 0, i, j;
  for ( i = a; i > 0; i -= lsb(i) )
    for  ( j = b; j > 0; j -= lsb(j) )
      if ( best[aib[i][j]] > ans ) ans = best[aib[i][j]];
  return ans;
}

void update ( int a, int b, int ind, int n )
{
  int i, j;
  for ( i = a; i <= n; i += lsb(i) )
    for ( j = b; j <= n; j += lsb(j) )
      if ( best[aib[i][j]] < best[ind] ) aib[i][j] = ind;
}

int main ()
{
  int n, t; fin >> n >> t;
  int i, j, z, _M;
  while (t--)
  {
    for ( i = 1; i <= n; i++ ) fin >> v[i].x >> v[i].y >> v[i].z;
    sort ( v+1, v+n+1, cmp );
    for ( _M = 0, i = 1; i <= n; i++ )
    {
      best[i] = 1 + query (v[i].x-1, v[i].y-1);
      update (v[i].x, v[i].y, i, n);
      umax (_M, best[i]);
    }
    fout << _M << '\n';
    for ( z = 1; z <= n; z++ )
      for ( i = v[z].x; i <= n; i += lsb(i) )
        for ( j = v[z].y; j <= n; j += lsb(j) ) aib[i][j] = 0;
  }
  fin.close (); fout.close ();
  return 0;
}