Cod sursa(job #1814111)

Utilizator Data 23 noiembrie 2016 17:45:06 Cutii 100 cpp done Arhiva de probleme 1.48 kb
``````#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>

using namespace std;

struct box{
int x, y, z;

box(){};
};

int cmp(box x, box y){
return x.x < y.x;
}

int boxes;
box gvn[3550];
int aib[3550][3550];

for(int i = 1; i <= boxes; ++i)
scanf("%d%d%d", &gvn[i].x, &gvn[i].y, &gvn[i].z);

sort(gvn + 1, gvn + boxes + 1, cmp);
}

int ans;

int lsb(int x){
return (x & (x - 1)) ^ x;
}

void update(int x, int y, int val){
for(int i = x; i <= boxes; i += lsb(i))
for(int j = y; j <= boxes; j += lsb(j))
aib[i][j] = max(aib[i][j], val);
}

void update0(int x, int y){
for(int i = x; i <= boxes; i += lsb(i))
for(int j = y; j <= boxes; j += lsb(j))
aib[i][j] = 0;
}

int query(int x, int y){
int mx = 0;
for(int i = x; i > 0; i -= lsb(i))
for(int j = y; j > 0; j -= lsb(j))
mx = max(aib[i][j], mx);
return mx;
}

void solve(){
ans = 0;
for(int i = 1; i <= boxes; ++i){
update(gvn[i].y, gvn[i].z, query(gvn[i].y - 1, gvn[i].z - 1) + 1);
ans = max(ans, query(gvn[i].y, gvn[i].z));
}
for(int i = 1; i <= boxes; ++i)
update0(gvn[i].y, gvn[i].z);
}

void write(){
printf("%d\n", ans);
}

int main(){
assert(freopen("cutii.in", "r", stdin));
assert(freopen("cutii.out", "w", stdout));

int cases;
scanf("%d%d", &boxes, &cases);

for(int i = 1; i <= cases; ++i){