Cod sursa(job #2528319)

Utilizator RedXtreme45Catalin RedXtreme45 Data 21 ianuarie 2020 19:08:52
Problema Cutii Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#define Nmax 3501
using namespace std;
ifstream fin("cutii.in");
ofstream fout("cutii.out");
int n,m,aib[Nmax][Nmax];
struct cutie{
    int x,y,z;
}v[Nmax];
int cmp(cutie a,cutie b)
{
    if (a.x!=b.x)
        return a.x<b.x;
    else
    {
        if (a.y!=b.y)
            return a.y<b.y;
        else
            return a.z<b.z;
    }
}
int suma(int poz1,int poz2)
{
    int S=0;
    for (int i=poz1;i>0;i-=(i&(-i)))
    {
        for (int j=poz2;j>0;j-=(j&(-j)))
        {
            S=max(aib[i][j],0);
        }
    }
    return S;
}
void update(int poz1,int poz2,int val)
{
    for (int i=poz1;i<=n;i+=(i&(-i)))
    {
        for (int j=poz2;j<=n;j+=(j&(-j)))
        {
            aib[i][j]+=val;
        }
    }
}
int main()
{
    fin>>n>>m;
    for (int i1=1;i1<=m;i1++)
    {
        memset(aib,0,sizeof aib);
        for (int j1=1;j1<=n;j1++)
        {
            fin>>v[j1].x>>v[j1].y>>v[j1].z;
        }
        sort (v+1,v+n+1,cmp);
        int i,j;
        for (i=1;i<=n;i++)
        {
            int q=suma(v[i].y-1,v[i].z-1)+1;
            update (v[i].y,v[i].z,q);
        }
        fout<<suma(n,n)<<"\n";
    }
    return 0;
}