Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <stack>
- using namespace std;
- int n;
- int map[1000002];
- int p1[1000002];
- int t[1000002];
- stack<int> st;
- int main() {
- cin>>n;
- for(int i=1; i<=n; i++)
- scanf("%d",&map[i]);
- t[1]=map[1];
- p1[1]=1;
- int pIndex=1;
- for(int i=2; i<=n; i++) {
- if(map[i]>t[pIndex]) {
- pIndex++;
- p1[i]=pIndex;
- t[pIndex]=map[i];
- } else {
- int lowIndex = lower_bound(t+1, t+pIndex, map[i])-t;
- p1[i]=lowIndex;
- t[lowIndex]=map[i];
- }
- }
- int len = pIndex;
- for(int i=n; i>=1; i--){
- if(p1[i]==len) {
- st.push(map[i]);
- len--;
- }
- }
- cout<<pIndex<<endl;
- while (!st.empty()) {
- printf("%d ",st.top());
- st.pop();
- }
- cout<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement