anasretdinov

Astack

May 18th, 2021
511
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.     #define ll long long
  2.     #include <iostream>
  3.     using namespace std;
  4.     #include <vector>
  5.     #include <stack>
  6.     //struct Node{
  7.     //    ll data;
  8.     //    Node *next;
  9.     //    Node();
  10.     //
  11.     //    Node(long long int data, Node *next) : data(data), next(next) {}
  12.     //};
  13.     //class LinkedList{
  14.     // public:
  15.     //    Node *s, *f;
  16.     //    int sz = 0;
  17.     //    LinkedList(){
  18.     //        s = nullptr, f = nullptr;
  19.     //    }
  20.     //    virtual ~LinkedList() {
  21.     //    }
  22.     //    void pushFront(int x){
  23.     //        Node *nw = new Node(x, nullptr);
  24.     //        if (s){
  25.     //            nw->next = s;
  26.     //            s = nw;
  27.     //        }
  28.     //        else{
  29.     //            nw->next = nullptr;
  30.     //            s = nw;
  31.     //            f = nw;
  32.     //        }
  33.     //        sz++;
  34.     //    }
  35.     //    void pushBack(int x){
  36.     //        Node *nw = new Node(x, nullptr);
  37.     //        nw->data = x;
  38.     //        nw->next = nullptr;
  39.     //        if (f){
  40.     //            f->next = nw;
  41.     //            f = nw;
  42.     //        }
  43.     //        else{
  44.     //            f = nw;
  45.     //            s = nw;
  46.     //        }
  47.     //        sz++;
  48.     //    }
  49.     //    int size(){
  50.     //        return sz;
  51.     //    }
  52.     //    int popFront(){
  53.     //        cout << "trying to pop...\n";
  54.     //        if (sz == 0){
  55.     //            cout << "size null\n";
  56.     //            return 0;
  57.     //        }
  58.     //        else{
  59.     //            cout << "popped " << s->data << '\n';
  60.     //            int ans = s->data;
  61.     //            s = s->next;
  62.     //            sz--;
  63.     //            return ans;
  64.     //        }
  65.     //    }
  66.     //    int popBack(){
  67.     //        if (sz == 0){
  68.     //            return 0;
  69.     //        }
  70.     //        if (sz == 1){
  71.     //            int ans = s->data;
  72.     //            s = nullptr;
  73.     //            f = nullptr;
  74.     //            sz--;
  75.     //            return ans;
  76.     //        }
  77.     //        Node *x = s;
  78.     //        while (x->next != f){
  79.     //            x = x -> next;
  80.     //        }
  81.     //        int ans = f->data;
  82.     //        f = x;
  83.     //        x->next = nullptr;
  84.     //        sz--;
  85.     //        return ans;
  86.     //    }
  87.     //};
  88.     //class Stack{
  89.     // public:
  90.     //    LinkedList l = LinkedList();
  91.     //    virtual ~Stack() {
  92.     //    }
  93.     //    void push(int x){
  94.     //        l.pushFront(x);
  95.     //    }
  96.     //    int pop(){
  97.     //        if (l.size() == 0) return 0;
  98.     //        else return l.popFront();
  99.     //    }
  100.     //    int size(){
  101.     //        return l.size();
  102.     //    }
  103.     //    int back(){
  104.     //        if (l.size() == 0) return 0;
  105.     //        return l.s->data;
  106.     //    }
  107.     //    void clear(){
  108.     //        l.sz = 0;
  109.     //        l.s = nullptr;
  110.     //        l.f = nullptr;
  111.     //    }
  112.     //};
  113.     //ostream& operator << (ostream &out, LinkedList ff){
  114.     //    if (ff.size() == 0){
  115.     //        return out;
  116.     //    }
  117.     //    Node *n = ff.s;
  118.     //    while (n->next != nullptr){
  119.     //        out << n->data << ' ';
  120.     //        n = n->next;
  121.     //    }
  122.     //    out << n->data << ' ';
  123.     //    return out;
  124.     //}
  125.     //ostream& operator << (ostream &out, Stack ss){
  126.     //    if (ss.size() == 0){
  127.     //        return out;
  128.     //    }
  129.     //    vector <int> f;
  130.     //    Node *n = ss.l.s;
  131.     //    while (n->next != nullptr){
  132.     //        f.push_back(n->data);
  133.     //        n = n->next;
  134.     //    }
  135.     //    f.push_back(n -> data);
  136.     //    for (int i : f){
  137.     //        out << i << ' ';
  138.     //    }
  139.     //    return out;
  140.     //}
  141.     //class Queue{
  142.     // public:
  143.     //    LinkedList l = LinkedList();
  144.     //    virtual ~Queue() {
  145.     //    }
  146.     //    void push(int x){
  147.     //        l.pushBack(x);
  148.     //    }
  149.     //    int pop(){
  150.     //        int ans = l.s->data;
  151.     //        l.popFront();
  152.     //        return ans;
  153.     //    }
  154.     //    int size(){
  155.     //        return l.sz;
  156.     //    }
  157.     //    int front(){
  158.     //        return l.s->data;
  159.     //    }
  160.     //    void clear(){
  161.     //        l.s = nullptr;
  162.     //        l.f = nullptr;
  163.     //        l.sz = 0;
  164.     //    }
  165.     //};
  166.     //ostream& operator << (ostream &out, Queue ss){
  167.     //    out << ss.l;
  168.     //    return out;
  169.     //}
  170.     int main() {
  171.         int n; cin >> n;
  172.         int a[n];
  173.         for (int i = 0; i < n; i++) cin >> a[i];
  174.         stack<int> st;
  175.         vector <int> ans (n, - 1);
  176.         for (int i = n - 1; i >= 0; i--){
  177.             while (!st.empty() && a[st.top()] <= a[i]) st.pop();
  178.             if (!st.empty()) ans[i] = st.top();
  179.             st.push(i);
  180.         }
  181.         for (int i = 0; i < n; i++) cout << ans[i] << ' ';
  182.     }
  183.  
RAW Paste Data