Cod sursa(job #2145951)

Utilizator Andrei_RAndrei Roceanu Andrei_R Data 27 februarie 2018 18:31:50
Problema Cutii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <string.h>
#define bit(i) i&-i
#define dim 3501
#include <algorithm>
using namespace std;
ifstream fin("cutii.in");
ofstream fout("cutii.out");
int aib[dim][dim],test,t,i,n,j,val;
struct cub
{
    int x;
    int y;
    int z;
}box[dim];
int cmp(cub o, cub p)
{
    return o.x<p.x;
}
void upDate(int pozy,int pozz,int val)
{
    for(int i=pozy;i<=n;i+=bit(i))
        for(int j=pozz;j<=n;j+=bit(j))
            aib[i][j]=max(aib[i][j],val);
}
void Clear(int pozy, int pozz)
{
    for(int i=pozy;i<=n;i+=bit(i))
        for(int j=pozz;j<=n;j+=bit(j))
            aib[i][j]=0;
}
int query(int pozy,int pozz)
{
    int Max=0;
    for(int i=pozy;i>0;i-=bit(i))
        for(int j=pozz;j>0;j-=bit(j))
            Max=max(Max,aib[i][j]);
    return Max;
}
int main()
{
    fin>>n>>test;
    for(t=1;t<=test;t++)
    {
        for(i=1;i<=n;i++)
            fin>>box[i].x>>box[i].y>>box[i].z;
        sort(box+1,box+1+n,cmp);
        for(i=1;i<=n;i++)
        {
            val=query(box[i].y-1,box[i].z-1);
            upDate(box[i].y,box[i].z,val+1);
        }
        fout<<query(n,n)<<'\n';
        for(i=1;i<=n;i++)
            Clear(box[i].y,box[i].z);
    }
    return 0;
}