제출 #464700

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
464700		AlexLuchianov	케이크 (CEOI14_cake)	C++14	0 / 100	2096 ms	19092 KiB

cake

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using ll = long long;

class SegmentTree{
private:
  std::vector<int> aint;
public:
  SegmentTree(int n) {
    aint.resize(1 + 4 * n);
  }
  void update(int node, int from, int to, int x, int val) {
    if(from < to) {
      int mid = (from + to) / 2;
      if(x <= mid)
        update(node * 2, from, mid, x, val);
      else
        update(node * 2 + 1, mid + 1, to, x, val);
      aint[node] = std::max(aint[node * 2], aint[node * 2 + 1]);
    } else
      aint[node] = val;
  }
  int query(int node, int from, int to, int x, int y) {
    if(from == x && to == y)
      return aint[node];
    else {
      int mid = (from + to) / 2;
      if(x <= mid && y <= mid)
        return query(node * 2, from, mid, x, y);
      else if(mid + 1 <= x && mid + 1 <= y)
        return query(node * 2 + 1, mid + 1, to, x, y);
      else
        return std::max(query(node * 2, from, mid, x, mid),
               query(node * 2 + 1, mid + 1, to, mid + 1, to));
    }
  }

  int firstBiggerLeft(int node, int from, int to, int x, int target) {
    if(x == from - 1)
      return x;
    if(from < to) {
      int mid = (from + to) / 2;
      if(x <= mid)
        return firstBiggerLeft(node * 2, from, mid, x, target);
      else {
        if(x == to && aint[node] < target)
          return from - 1;
        int result = firstBiggerLeft(node * 2 + 1, mid + 1, to, x, target);
        if(mid == result)
          return firstBiggerLeft(node * 2, from, mid, x, target);
        else
          return result;
      }
    } else {
      if(target < aint[node])
        return from;
      else
        return from - 1;
    }
  }

  int firstBiggerRight(int node, int from, int to, int x, int target) {
    
    if(x == to + 1)
      return x;

    if(from < to) {
      int mid = (from + to) / 2;
      if(mid + 1 <= x)
        return firstBiggerRight(node * 2 + 1, mid + 1, to, x, target);
      else {
        if(x == from && aint[node] < target)
          return to + 1;
        int result = firstBiggerRight(node * 2, from, mid, x, target);
        if((mid + 1) == result)
          return firstBiggerRight(node * 2 + 1, mid + 1, to, x, target);
        else
          return result;
      }
    } else {
      if(target < aint[node])
        return from;
      else
        return from + 1;
    }
  }
};

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n, start;
  std::cin >> n >> start;
  std::vector<int> v(1 + n);
  for(int i = 1;i <= n; i++) 
    std::cin >> v[i];
  int q;
  std::cin >> q;
  SegmentTree aint(n);

  std::set<std::pair<int,int>> myset;
  
  int ptr = n;
  for(int i = 1; i <= n; i++) {
    aint.update(1, 1, n, i, v[i]);
    myset.insert({v[i], i});
  }

  for(int i = 1; i <= q; i++) {
    char op;
    std::cin >> op;
    if(op == 'E') {
      int pos, val;
      std::cin >> pos >> val;
      std::vector<int> aux;
      std::set<std::pair<int,int>>::iterator it = myset.end();
      it--;
      for(int j = 1; j < val; j++) {
        aux.push_back(it->second);
        myset.erase(it--);
      }
      myset.erase({v[pos], pos});
      aux.push_back(pos);
      std::reverse(aux.begin(), aux.end());
      
      for(int j = 0; j < aux.size(); j++) {
        aint.update(1, 1, n, aux[j], ++ptr);
        myset.insert({ptr, aux[j]});
        v[aux[j]] = ptr;
      }

    } else {
      int pos;
      std::cin >> pos;
      if(start == pos)
        std::cout << 0 << '\n';
      else if(start < pos){
        int val = aint.query(1, 1, n, start + 1, pos);
        std::cout << (pos - aint.firstBiggerLeft(1, 1, n, start - 1, val) - 1) << '\n';
      } else {
        int val = aint.query(1, 1, n, pos, start - 1);
        std::cout << (aint.firstBiggerRight(1, 1, n, start + 1, val) - pos - 1) << '\n';
      }
    }
  }

  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

cake.cpp: In function 'int main()':
cake.cpp:130:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |       for(int j = 0; j < aux.size(); j++) {
      |                      ~~^~~~~~~~~~~~

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