oj.uz

Submission #464704

# Submission time Handle Problem Language Result Execution time Memory
464704 2021-08-13T18:22:56 Z AlexLuchianov Cake (CEOI14_cake) C++14
100 / 100
 1165 ms 22980 KB 
#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, y));
    }
  }

  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(to <= x && 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;
}

Compilation message

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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 6 ms 332 KB Output is correct
5 Correct 17 ms 972 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 844 KB Output is correct
2 Correct 333 ms 972 KB Output is correct
3 Correct 388 ms 972 KB Output is correct
4 Correct 249 ms 972 KB Output is correct
5 Correct 726 ms 1868 KB Output is correct
6 Correct 532 ms 1868 KB Output is correct
7 Correct 437 ms 1868 KB Output is correct
8 Correct 288 ms 1868 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 7936 KB Output is correct
2 Correct 108 ms 7476 KB Output is correct
3 Correct 82 ms 7696 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 286 ms 18228 KB Output is correct
6 Correct 274 ms 18056 KB Output is correct
7 Correct 143 ms 17932 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 568 KB Output is correct
2 Correct 42 ms 688 KB Output is correct
3 Correct 111 ms 3908 KB Output is correct
4 Correct 124 ms 3812 KB Output is correct
5 Correct 168 ms 732 KB Output is correct
6 Correct 188 ms 5788 KB Output is correct
7 Correct 163 ms 1428 KB Output is correct
8 Correct 273 ms 6968 KB Output is correct
9 Correct 1165 ms 22880 KB Output is correct
10 Correct 528 ms 1476 KB Output is correct
11 Correct 680 ms 2908 KB Output is correct
12 Correct 1139 ms 19408 KB Output is correct
13 Correct 875 ms 22980 KB Output is correct