Cod sursa(job #2633804)

Utilizator stefan.popescuPopescu Stefan stefan.popescu Data 8 iulie 2020 17:24:36
Problema Cutii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in ("cutii.in");
ofstream out("cutii.out");
int n, t, x, y, z;
vector < pair <int, int> > boxes;
vector < vector <int> > dp;
inline int look(int x, int y)
{
    int maxi=0;
    while(x>0)
    {
        int yp=y;
        while(yp>0)
        {
            maxi=max(maxi, dp[x][yp]);
            yp-=yp&(-yp);
        }
        x-=x&(-x);
    }
    return maxi;
}
inline void update(int x, int y, int val)
{
    if(val==0)
    {
        while(x<=n)
        {
            int yp=y;
            while(yp<=n)
            {
                dp[x][yp]=0;
                yp+=yp&(-yp);
            }
            x+=x&(-x);
        }
        return;
    }

    while(x<=n)
    {
        int yp=y;
        while(yp<=n)
        {
            dp[x][yp]=max(dp[x][yp], val);
            yp+=yp&(-yp);
        }
        x+=x&(-x);
    }
}

int main()
{
    in>>n>>t;
    boxes.resize(n+1);
    dp.resize(n+1, vector <int> (n+1, 0));
    while(t--)
    {
        int maxx=0;
        for(int i=1; i<=n; i++)
            in>>x>>y>>z, boxes[x]={y, z};

        for(int i=1; i<=n; i++)
        {
            int val=look(boxes[i].first-1, boxes[i].second-1)+1;
            update(boxes[i].first, boxes[i].second, val);
            maxx=max(maxx, val);
        }
        for(int i=1; i<=n; i++)
            update(boxes[i].first, boxes[i].second, 0);
        out<<maxx<<"\n";
    }
    return 0;
}