Submission #51232513

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using int64 = long long;
using uint = unsigned int;
using uint64 = unsigned long long;
bool ckmin(auto& a, auto b) { return b < a ? a = b, 1 : 0; }
bool ckmax(auto& a, auto b) { return b > a ? a = b, 1 : 0; }
using namespace std;

struct Node {
  int val;
  Node* prev;
  Node* next;
  Node(int val) : val(val) {}
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  map<int, Node*> go;

  auto Insert = [&](int x, int y) {
    assert(go.contains(x));
    Node* xx = go[x];
    Node* yy = new Node(y);
    xx->next->prev = yy;
    yy->next = xx->next;
    yy->prev = xx;
    xx->next = yy;
    go[y] = yy;
  };

  auto Delete = [&](int x) {
    assert(go.contains(x));
    Node* xx = go[x];
    xx->prev->next = xx->next;
    xx->next->prev = xx->prev;
    go.erase(x);
  };

  auto head = new Node(-1), tail = new Node(-2);
  head->next = tail;
  tail->prev = head;
  go[-1] = head, go[-2] = tail;
  for (int i = n - 1; i >= 0; i--) Insert(-1, a[i]);

  int q;
  cin >> q;
  while (q--) {
    int op, x, y;
    cin >> op >> x;
    if (op == 1) {
      cin >> y;
      Insert(x, y);
    } else {
      Delete(x);
    }
  }

  for (auto x = head->next; x != tail; x = x->next) {
    cout << x->val << ' ';
  }
  cout << '\n';

  return 0;
}

Submission Info

Judge Result