제출 #105059

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105059		WLZ	Cake (CEOI14_cake)	C++17	100 / 100	1157 ms	51964 KiB

cake

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int n, a;
vector<int> d, top10;

struct node {
  int i, j;
  node *left, *right;
  int val;
};

node* build(int i, int j) {
  if (i == j) {
    return new node{i, j, nullptr, nullptr, 0};
  }
  node* left = build(i, (i + j) / 2);
  node* right = build((i + j) / 2 + 1, j);
  return new node{i, j, left, right, max(left->val, right->val)};
}

int query_mx(node* cur, int i, int j) {
  if (cur->i > j || cur->j < i) {
    return -INF;
  }
  if (cur->i >= i && cur->j <= j) {
    return cur->val;
  }
  return max(query_mx(cur->left, i, j), query_mx(cur->right, i, j));
}

void update(node* cur, int i, int newVal) {
  if (cur->i > i || cur->j < i) {
    return;
  }
  if (cur->i == i && cur->j == i) {
    cur->val = newVal;
    return;
  }
  update(cur->left, i, newVal);
  update(cur->right, i, newVal);
  cur->val = max(cur->right->val, cur->left->val);
}

int find(node* cur, int val, int dir) {
  if (cur->i == cur->j) {
    if (dir) {
      return cur->i + (cur->val < val);
    } else {
      return cur->i - (cur->val < val);
    }
  }
  if (dir) {
    if (cur->left->val < val) {
      return find(cur->right, val, dir);
    }
    return find(cur->left, val, dir);
  } else {
    if (cur->right->val < val) {
      return find(cur->left, val, dir);
    }
    return find(cur->right, val, dir);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> a;
  d.resize(n + 1);
  node* rootl = build(1, n);
  node* rootr = build(1, n);
  for (int i = 1; i <= n; i++) {
    cin >> d[i];
    if (i < a) {
      update(rootl, i, d[i]);
    } else if (i > a) {
      update(rootr, i, d[i]);
    }
    top10.push_back(i);
  }
  sort(top10.begin(), top10.end(), [](const int& a, const int& b) {
    return d[a] > d[b];
  });
  while ((int) top10.size() > 10) {
    top10.pop_back();
  }
  int q;
  cin >> q;
  while (q--) {
    char t;
    cin >> t;
    if (t == 'E') {
      int i, e;
      cin >> i >> e;
      e--;
      for (auto it = top10.begin(); it != top10.end(); it++) {
        if (*it == i) {
          top10.erase(it);
          break;
        }
      }
      for (int j = 0; j < e; j++) {
        d[top10[j]]++;
        if (top10[j] < a) {
          update(rootl, top10[j], d[top10[j]]);
        } else if (top10[j] > a) {
          update(rootr, top10[j], d[top10[j]]);
        }
      }
      d[i] = d[top10[e]] + 1;
      top10.insert(top10.begin() + e, i);
      while ((int) top10.size() > 10) {
        top10.pop_back();
      }
      if (i < a) {
        update(rootl, i, d[i]);
      } else if (i > a) {
        update(rootr, i, d[i]);
      }
    } else {
      int b;
      cin >> b;
      if (b < a) {
        cout << find(rootr, query_mx(rootl, b, a - 1), 1) - b - 1;
      } else if (b > a) {
        cout << b - 1 - find(rootl, query_mx(rootr, a + 1, b), 0);
      } else {
        cout << 0;
      }
      cout << '\n';
    }
  }
  return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50