oj.uz

Submission #464700

# Submission time Handle Problem Language Result Execution time Memory
464700 2021-08-13T18:03:07 Z AlexLuchianov Cake (CEOI14_cake) C++14
0 / 100
 2000 ms 19092 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, 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;
}

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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 572 ms 5244 KB Output isn't correct
2 Correct 332 ms 5320 KB Output is correct
3 Correct 394 ms 5320 KB Output is correct
4 Correct 261 ms 5320 KB Output is correct
5 Incorrect 640 ms 6596 KB Output isn't correct
6 Incorrect 533 ms 6952 KB Output isn't correct
7 Correct 432 ms 6820 KB Output is correct
8 Correct 303 ms 6960 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 7852 KB Time limit exceeded
2 Execution timed out 2074 ms 8596 KB Time limit exceeded
3 Execution timed out 2078 ms 8232 KB Time limit exceeded
4 Correct 1 ms 204 KB Output is correct
5 Execution timed out 2079 ms 19092 KB Time limit exceeded
6 Execution timed out 2093 ms 18740 KB Time limit exceeded
7 Execution timed out 2092 ms 18852 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 189 ms 964 KB Output isn't correct
2 Incorrect 213 ms 1128 KB Output isn't correct
3 Execution timed out 2095 ms 4664 KB Time limit exceeded
4 Incorrect 1675 ms 4772 KB Output isn't correct
5 Incorrect 271 ms 1860 KB Output isn't correct
6 Execution timed out 2096 ms 5792 KB Time limit exceeded
7 Incorrect 246 ms 2972 KB Output isn't correct
8 Incorrect 633 ms 9392 KB Output isn't correct
9 Execution timed out 2073 ms 18908 KB Time limit exceeded
10 Incorrect 954 ms 5244 KB Output isn't correct
11 Incorrect 1311 ms 7420 KB Output isn't correct
12 Execution timed out 2092 ms 15340 KB Time limit exceeded
13 Execution timed out 2087 ms 18888 KB Time limit exceeded