Pagini recente » Borderou de evaluare (job #2566814) | Cod sursa (job #2712170)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cutii.in");
ofstream fout("cutii.out");
const int nmax = 3500;
int n, t, dp[nmax], aib[nmax][nmax];
int Query(int i, int j){
int aux = j, maxx = 0;
for (; i >= 1; i -= i&(-i)){
j = aux;
for (; j >= 1; j -= j&(-j)){
maxx = max(maxx, aib[i][j]);
}
}
return maxx;
}
void Update(int i, int j, int add){
int aux = j;
for (; i <= n; i += i&(-i)){
j = aux;
for (; j <= n; j += j&(-j)){
aib[i][j] = max(aib[i][j], add);
}
}
}
struct cutie{
int x, y, z;
bool operator < (cutie &c) const{
if (x == c.x){
if (y == c.y)
return z < c.z;
return y < c.y;
}
return x < c.x;
}
}v[nmax];
int main(){
fin >> n >> t;
while (t--){
for (int i = 1; i <= n; ++i){
fin >> v[i].x >> v[i].y >> v[i].z;
}
sort(v + 1, v + n + 1);
int maxim = 0, j = 1;
memset(aib, 0, sizeof aib);
for (int i = 1; i <= n; ++i){
while (j < i && v[i].x != v[j].x){
Update(v[j].y, v[j].z, dp[j]);
++j;
}
dp[i] = 1 + Query(v[i].y - 1, v[i].z - 1);
maxim = max(maxim, dp[i]);
}
fout << maxim << "\n";
}
return 0;
}