#include <bits/stdc++.h>
#define pb push_back
#define X first
#define Y second
#define pii pair<int, int>
#define lb lower_bound
using namespace std;
int n, x;
vector<int> in, srt;
struct ft{
vector<int> fen;
ft(int N){
fen.assign(N+1, 0);
}
int qer(int a){
a++;
int ans = 0;
for(;a>0; a-=a&(-a))ans=max(ans, fen[a]);
return ans;
}
void upd(int a, int b){
a++;
for(;a<fen.size(); a+=a&(-a))fen[a]=max(b, fen[a]);
}
};
int main(){
cin >> n >> x;
for(int i = 0; i<n; i++){
int c; cin >> c;
in.pb(c); srt.pb(c);
}
sort(srt.begin(), srt.end());
ft yes(n), no(n);
for(auto i : in){
int id = lb(srt.begin(), srt.end(), i)-srt.begin();
int tmp = no.qer(id-1);
no.upd(id, tmp+1);
tmp = yes.qer(id-1);
int nid = lb(srt.begin(), srt.end(), i+x)-srt.begin();
int tmp2 = no.qer(nid-1);
tmp = max(tmp, tmp2);
yes.upd(id, tmp+1);
}
cout << yes.qer(n-1);
return 0;
}
Compilation message
glo.cpp: In member function 'void ft::upd(int, int)':
glo.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;a<fen.size(); a+=a&(-a))fen[a]=max(b, fen[a]);
~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
172 ms |
5768 KB |
Output is correct |
2 |
Correct |
180 ms |
5700 KB |
Output is correct |
3 |
Correct |
173 ms |
5756 KB |
Output is correct |
4 |
Correct |
169 ms |
5700 KB |
Output is correct |
5 |
Correct |
102 ms |
4856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
41 ms |
1772 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
3180 KB |
Output is correct |
2 |
Correct |
76 ms |
3024 KB |
Output is correct |
3 |
Correct |
158 ms |
5604 KB |
Output is correct |
4 |
Correct |
124 ms |
4836 KB |
Output is correct |
5 |
Correct |
51 ms |
2668 KB |
Output is correct |
6 |
Correct |
95 ms |
4704 KB |
Output is correct |
7 |
Correct |
118 ms |
5348 KB |
Output is correct |
8 |
Correct |
70 ms |
3180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |