#include <bits/stdc++.h>
using namespace std;
struct Fenwick{
vector<int> arr;
int n;
bool startFromLeft;
Fenwick(int _n, bool _startFromLeft){
//0 to n-1 inclusive
startFromLeft = _startFromLeft;
n=_n;
arr.resize(n+1);
}
int conv(int ind){
ind+=1;
if (!startFromLeft){
ind=n+1-ind;
}
return ind;
}
void update(int ind, int val){
ind = conv(ind);
while (ind<=n){
arr[ind]=max(arr[ind],val);
ind+=ind&(-ind);
}
}
int query(int ind){
ind = conv(ind);
int val = 0;
while (ind>0){
val=max(val,arr[ind]);
ind-=ind&(-ind);
}
return val;
}
};
vector<int> vals;
vector<int> mp;
vector<int> lisl;
vector<int> lisr;
int main(){
int n,d;
cin>>n>>d;
vals.resize(n);
mp.resize(n);
for (int i = 0; i<n; i++){
cin>>vals[i];
mp[i]=vals[i];
}
sort(mp.begin(),mp.end());
mp.erase(unique(mp.begin(),mp.end()),mp.end());
for (int i = 0; i<n; i++){
vals[i]=lower_bound(mp.begin(),mp.end(),vals[i])-mp.begin();
}
Fenwick *fenl = new Fenwick(n+1, true);
lisl.resize(n,0);
for (int i = 0; i<n; i++){
//cout<<vals[i]<<'\n';
int mxprev = fenl->query(vals[i]);
lisl[i]=mxprev+1;
fenl->update(vals[i]+1,lisl[i]);
}
Fenwick *fenr = new Fenwick(n+1, false);
lisr.resize(n,0);
int mx = 0;
for (int i = n-1; i>=0; i--){
//cout<<vals[i]<<'\n';
int mxprev = fenr->query(vals[i]+1);
lisr[i]=mxprev+1;
fenr->update(vals[i],lisr[i]);
mx=max(mx,lisr[i]);
}
cout<<mx<<'\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
205 ms |
4984 KB |
Output is correct |
2 |
Correct |
193 ms |
5016 KB |
Output is correct |
3 |
Correct |
189 ms |
5088 KB |
Output is correct |
4 |
Correct |
198 ms |
5112 KB |
Output is correct |
5 |
Correct |
119 ms |
4984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
47 ms |
1528 KB |
Output is correct |
2 |
Correct |
49 ms |
1528 KB |
Output is correct |
3 |
Correct |
48 ms |
1528 KB |
Output is correct |
4 |
Incorrect |
32 ms |
1536 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
94 ms |
2680 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
256 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |