Cod sursa(job #1073421)

Utilizator alexpascadiAlexandru Pascadi alexpascadi Data 6 ianuarie 2014 10:47:47
Problema Cutii Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>
#include <fstream>
using namespace std;

const int N=3501;
int r[N][N],n,T,v1[N],v2[N],v[4];
char s[20];

int query(int i, int j)
{
    int dmax=0,p=i,q;
    while(p>0)
    {
        q=j;
        while(q>0)
        {
            if(r[p][q]>dmax) dmax=r[p][q];
            q-=q&-q;
        }
        p-=p&-p;
    }
    return dmax;
}

void update(int i, int j, int val)
{
    int p=i,q;
    while(p<=n)
    {
        q=j;
        while(q<=n)
        {
            if(r[p][q]<val) r[p][q]=val;
            q+=q&-q;
        }
        p+=p&-p;
    }
}

int main()
{
    ifstream in("cutii.in");
    FILE *out;
    out=fopen("cutii.out","w");
    int k,i,j,x,y,z,maxim,rez;
    in>>n>>T>>ws;
    for(k=1;k<=T;k++)
    {
        for(i=1;i<=n;i++)
        {
            in>>x>>y>>z;
            v1[x]=y;
            v2[x]=z;
        }

        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                r[i][j]=0;

        maxim=-1;

        for(i=1;i<=n;i++)
        {
            rez=query(v1[i],v2[i])+1;
            update(v1[i],v2[i],rez);
            if(maxim<rez) maxim=rez;
        }

        fprintf(out,"%d\n",maxim);
    }

    return 0;
}