# Cod sursa(job #2498355)

Utilizator Data 23 noiembrie 2019 20:26:20 Cutii 100 cpp-64 done Arhiva de probleme 1.44 kb
``````#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin ("cutii.in");
ofstream cout ("cutii.out");

#define x first
#define y second.first
#define z second.second

using PI = pair<int, int>;
using PII = pair<int, PI>;
using VPII = vector<PII>;
using VI = vector<int>;
using VVI = vector<VI>;

int n, t;
VPII a;
VVI aib;

void update(int, int, int);
int query(int, int);
void solve();

int main()
{
cin >> n >> t;

a = VPII(n + 1);
aib = VVI(n + 1, VI(n + 1));
while (t --)
solve();
return 0;
}
void update(int x2, int y2, int val)
{
for (int x1 = x2; x1 <= n; x1 += x1 & -x1)
for (int y1 = y2; y1 <= n; y1 += y1 & -y1)
if (val == -1)aib[x1][y1] = 0;
else aib[x1][y1] = max(aib[x1][y1], val);
}
int query(int x2, int y2)
{
int rez = 0;
for (int x1 = x2; x1 > 0; x1 -= x1 & -x1)
for (int y1 = y2; y1 > 0; y1 -= y1 & -y1)
rez = max(rez, aib[x1][y1]);
return rez;
}
void solve()
{
for (int i = 1; i <= n; ++ i)
cin >> a[i].x >> a[i].y >> a[i].z;
sort(a.begin() + 1, a.end());

int dmax = 0;
for (int i = 1, d; i <= n; ++ i)
{
d = query(a[i].y - 1, a[i].z - 1) + 1;
update(a[i].y, a[i].z, d);
dmax = max(dmax, d);
}
for (int i = 1; i <= n; ++ i)
update(a[i].y, a[i].z, -1);
cout << dmax << '\n';
}
``````