#include <bits/stdc++.h>
const int inf = 1e9+900;
struct Node {
Node* left,*right;
int val;
int l,r;
};
Node* novonode(void){
Node* x = (Node*)calloc(sizeof(Node),1);
return x;
}
int update(int t,int k,Node* v){
int la=v->l,ra=v->r;
if(t<la||ra<t)return 0;
if(la==ra){
v->val=std::max(v->val,k);
return k;
}
int m = (la+ra)/2;
if(!v->left){
Node* k = novonode();
v->left=k;
k->l=la;
k->r=m;
}
if(!v->right){
Node* k = novonode();
v->right=k;
k->l=m+1;
k->r=ra;
}
int a = update(t,k,v->left);
int b = update(t,k,v->right);
v->val=std::max(v->left->val,v->right->val);
return v->val;
}
int query(int l,int r,Node* v){
int la=v->l,ra=v->r;
if(r<la||ra<l)return 0;
if(la>=l&&ra<=r){
return v->val;
}
int m = (la+ra)/2;
if(!v->left){
Node* k = novonode();
v->left=k;
k->l=la;
k->r=m;
}
if(!v->right){
Node* k = novonode();
v->right=k;
k->l=m+1;
k->r=ra;
}
int a = query(l,r,v->left);
int b = query(l,r,v->right);
return std::max(a,b);
}
Node inicio;
const int val = 1e8;
int main()
{
inicio.l=0;
inicio.r=+1e9+10000;
int N,T;
std::cin>>N>>T;
int array[N];for(auto&x:array)std::cin>>x;
for(int i=0;i!=N;++i){
int x=array[i];
int melhor = query(0,x-1,&inicio);
update(x,melhor+1,&inicio);
}
std::cout<<(query(0,inf,&inicio))<<"\n";
}
Compilation message
glo.cpp: In function 'int update(int, int, Node*)':
glo.cpp:32:9: warning: unused variable 'a' [-Wunused-variable]
32 | int a = update(t,k,v->left);
| ^
glo.cpp:33:9: warning: unused variable 'b' [-Wunused-variable]
33 | int b = update(t,k,v->right);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
592 ms |
236012 KB |
Output is correct |
2 |
Correct |
617 ms |
236060 KB |
Output is correct |
3 |
Correct |
646 ms |
236036 KB |
Output is correct |
4 |
Correct |
631 ms |
236024 KB |
Output is correct |
5 |
Correct |
321 ms |
128076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
143 ms |
68536 KB |
Output is correct |
2 |
Correct |
151 ms |
68572 KB |
Output is correct |
3 |
Correct |
145 ms |
68544 KB |
Output is correct |
4 |
Incorrect |
90 ms |
36912 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
296 ms |
127580 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |