oj.uz

Submission #781068

# Submission time Handle Problem Language Result Execution time Memory
781068 2023-07-12T16:55:14 Z tvladm2009 Abracadabra (CEOI22_abracadabra) C++17
0 / 100
 473 ms 33376 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 2e5 + 7;
const int Q = (int) 1e6 + 7;
const int INF = (int) 1e9;
int a[N], sol[Q];
vector<pair<int, int>> questions[N];
int n, q;

mt19937 rng;

int gen() {
  return uniform_int_distribution<int>(INF)(rng);
}

struct Node {
  int val;
  int sz;
  int prio;
  int mx;
  Node* left;
  Node* right;

  Node(int val_ = 0) {
    val = val_;
    mx = val_;
    sz = 1;
    prio = gen();
    left = NULL;
    right = NULL;
  }
};

struct Treap {
  int getsize(Node* &root) {
    if (root == NULL) {
      return 0;
    } else {
      return root->sz;
    }
  }

  int getmax(Node* &root) {
    if (root == NULL) {
      return 0;
    } else {
      return root->mx;
    }
  }

  void compute(Node* &root) {
    root->sz = 1 + getsize(root->left) + getsize(root->right);
    root->mx = max({getmax(root->left), root->val, getmax(root->right)});
  }

  pair<Node*, Node*> split(Node* &root, int target) { /// dupa val
    if (root == NULL) {
      return {NULL, NULL};
    } else if (root->val <= target) {
      pair<Node*, Node*> sol = split(root->right, target);
      root->right = sol.first;
      compute(root);
      return {root, sol.second};
    } else {
      pair<Node*, Node*> sol = split(root->left, target);
      root->left = sol.second;
      compute(root);
      return {sol.first, root};
    }
  }

  pair<Node*, Node*> splitSize(Node* &root, int target) { /// dupa size
    if (root == NULL) {
      return {NULL, NULL};
    }
    int cnt = getsize(root->left) + 1;
    if (cnt <= target) {
      pair<Node*, Node*> sol = splitSize(root->right, target - cnt);
      root->right = sol.first;
      compute(root);
      return {root, sol.second};
    } else {
      pair<Node*, Node*> sol = splitSize(root->left, target);
      root->left = sol.second;
      compute(root);
      return {sol.first, root};
    }
  }

  Node* _merge(Node* &a, Node* &b) {
    if (a == NULL && b == NULL) {
      return NULL;
    } else if (a == NULL) {
      return b;
    } else if (b == NULL) {
      return a;
    } else if (a->prio < b->prio) {
      a->right = _merge(a->right, b);
      compute(a);
      return a;
    } else {
      b->left = _merge(a, b->left);
      compute(b);
      if (b != NULL) {
        b->mx = max({b->val, getmax(b->left), getmax(b->right)});
      }
      return b;
    }
  }

  int _kth(Node* &root, int k) {
    if (root == NULL) {
      return -1;
    }
    int cnt = getsize(root->left) + 1;
    if (cnt == k) {
      return root->val;
    } else if (cnt < k) {
      return _kth(root->right, k - cnt);
    } else {
      return _kth(root->left, k);
    }
  }

  Node* root;
  Treap() {
    root = NULL;
  }
  void _insert(int val) {
    pair<Node*, Node*> sol = split(root, val);
    Node* newnode = new Node(val);
    sol.first = _merge(sol.first, newnode);
    root = _merge(sol.first, sol.second);
  }
  int _query(int val) {
    pair<Node*, Node*> sol = split(root, val - 1);
    int ret = getsize(sol.second);
    root = _merge(sol.first, sol.second);
    return ret;
  }
  pair<Node*, Node*> extractSize(int target) {
    return splitSize(root, target);
  }
  pair<Node*, Node*> extractMax(int target) {
    return split(root, target);
  }
  void mergee(Node *aux) {
    root = _merge(root, aux);
  }
  int kth(int x) {
    return _kth(root, x);
  }
  void del() {
    root = NULL;
  }
};

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  // freopen("input", "r", stdin);

  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= q; i++) {
    int t, x;
    cin >> t >> x;
    questions[min(t, n)].push_back({x, i});
  }
  Treap t;
  for (int i = 1; i <= n; i++) {
    Node* aux;
    aux = new Node(a[i]);
    t.mergee(aux);
  }
  for (int lap = 0; lap <= n; lap++) {
    if (lap != 0) {
      Treap x, y;
      pair<Node*, Node*> aux = t.extractSize(n / 2);
      x.root = aux.first;
      y.root = aux.second;
      t.del();
      while (x.root != NULL && y.root != NULL) {
        int vv = y.kth(1);
        Treap z, zz;
        if (vv < x.root->mx) {
          pair<Node*, Node*> aux = x.extractMax(vv);
          z.root = aux.first;
          x.root = aux.second;
          int big = INF;
          if (y.root != NULL) {
            big = x.kth(1);
          }
          aux = y.extractMax(big);
          zz.root = aux.first;
          y.root = aux.second;

          t.mergee(z.root);
          t.mergee(zz.root);
        } else {
          break;
        }
      }
      t.mergee(x.root);
      t.mergee(y.root);
    }
    for (auto &it : questions[lap]) {
      sol[it.second] = t.kth(it.first);
    }
  }
  for (int i = 1; i <= q; i++) {
    cout << sol[i] << "\n";
  }
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 23068 KB Output is correct
2 Correct 245 ms 21916 KB Output is correct
3 Correct 238 ms 21448 KB Output is correct
4 Incorrect 211 ms 21308 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 33376 KB Output is correct
2 Correct 378 ms 33304 KB Output is correct
3 Correct 320 ms 28972 KB Output is correct
4 Incorrect 337 ms 29156 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 13172 KB Output is correct
2 Correct 141 ms 12544 KB Output is correct
3 Correct 109 ms 12536 KB Output is correct
4 Incorrect 98 ms 12128 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 23068 KB Output is correct
2 Correct 245 ms 21916 KB Output is correct
3 Correct 238 ms 21448 KB Output is correct
4 Incorrect 211 ms 21308 KB Output isn't correct
5 Halted 0 ms 0 KB -