999ms

Untitled

Oct 23rd, 2021
571
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. #define all(x) begin(x), end(x)
  5.  
  6. using namespace std;
  7. using namespace __gnu_pbds;
  8. using ll = long long;
  9. template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  10.  
  11.  
  12. void solve() {
  13.   int n;
  14.   cin >> n;
  15.   bool flag = false;
  16.   ordered_set<int> cur;
  17.   for (int i = 0; i < n; ++i) {
  18.     int x;
  19.     cin >> x;
  20.     if (flag) {
  21.       cout << "No\n";
  22.       continue;
  23.     }
  24.     auto it = cur.find(x);
  25.     if (it == cur.end()) {
  26.       cur.insert(x);
  27.       cout << "Yes\n";
  28.       continue;
  29.     }
  30.     if (cur.order_of_key(x) + 1 == x && cur.size() > x) {
  31.       cout << "No\n";
  32.       continue;
  33.     }
  34.     while (*it == x) {
  35.       x--;
  36.       if (it == cur.begin()) {
  37.         cur.erase(it);
  38.         break;
  39.       } else {
  40.         auto pre = *prev(it);
  41.         cur.erase(it);
  42.         it = cur.find(pre);
  43.       }
  44.     }
  45.     flag = x == 0;
  46.     cur.insert(x);
  47.     cout << "Yes\n";
  48.   }
  49. }
  50.  
  51. int main() {
  52.   ios_base::sync_with_stdio(false);
  53.   cin.tie(nullptr);
  54.   solve();
  55. }
RAW Paste Data