oj.uz

Submission #464703

# Submission time Handle Problem Language Result Execution time Memory
464703 2021-08-13T18:15:03 Z AlexLuchianov Cake (CEOI14_cake) C++14
30 / 100
 2000 ms 17356 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(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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 8 ms 332 KB Output is correct
5 Correct 52 ms 1132 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 1100 KB Output is correct
2 Correct 335 ms 1228 KB Output is correct
3 Correct 406 ms 1220 KB Output is correct
4 Correct 259 ms 1228 KB Output is correct
5 Correct 631 ms 2124 KB Output is correct
6 Correct 532 ms 2124 KB Output is correct
7 Correct 444 ms 2124 KB Output is correct
8 Correct 290 ms 2228 KB Output is correct

Subtask #3
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 7424 KB Time limit exceeded
2 Execution timed out 2075 ms 7416 KB Time limit exceeded
3 Execution timed out 2074 ms 7476 KB Time limit exceeded
4 Correct 0 ms 204 KB Output is correct
5 Execution timed out 2085 ms 17244 KB Time limit exceeded
6 Execution timed out 2063 ms 17356 KB Time limit exceeded
7 Execution timed out 2066 ms 17220 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 836 KB Output is correct
2 Correct 203 ms 988 KB Output is correct
3 Execution timed out 2065 ms 4148 KB Time limit exceeded
4 Correct 1517 ms 4144 KB Output is correct
5 Correct 273 ms 936 KB Output is correct
6 Execution timed out 2082 ms 5016 KB Time limit exceeded
7 Correct 248 ms 1620 KB Output is correct
8 Correct 544 ms 7232 KB Output is correct
9 Execution timed out 2081 ms 17340 KB Time limit exceeded
10 Correct 888 ms 1736 KB Output is correct
11 Correct 1235 ms 3140 KB Output is correct
12 Execution timed out 2078 ms 13972 KB Time limit exceeded
13 Execution timed out 2079 ms 17340 KB Time limit exceeded