oj.uz

답안 #680590

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680590 2023-01-11T10:29:33 Z peijar 케이크 (CEOI14_cake) C++17
83.3333 / 100
 2000 ms 50600 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXN = 1e6 + 1;
const int INF = 1e18;
int iDeb[MAXN], iFin[MAXN];
pair<int, int> seg[MAXN];
int beat[MAXN], lazy[MAXN];
vector<int> rang;

void pull(int node) { seg[node] = max(seg[2 * node], seg[2 * node + 1]); }

void push(int node) {
  if (lazy[node] == INF)
    return;
  int x = lazy[node];
  lazy[node] = INF;
  beat[node] = x;
  if (iDeb[node] < iFin[node])
    lazy[2 * node] = lazy[2 * node + 1] = x;
}

void build(int node, int l, int r) {
  iDeb[node] = l, iFin[node] = r;
  lazy[node] = INF;
  if (l == r)
    return;
  int m = (l + r) / 2;
  build(2 * node, l, m);
  build(2 * node + 1, m + 1, r);
}

void setPos(int node, int i, int x) {
  if (iDeb[node] > i or iFin[node] < i)
    return;
  if (iDeb[node] == iFin[node]) {
    seg[node] = pair(x, i);
    return;
  }
  setPos(2 * node, i, x);
  setPos(2 * node + 1, i, x);
  pull(node);
}

void rangeSet(int node, int l, int r, int x) {
  push(node);
  if (iDeb[node] > r or iFin[node] < l)
    return;
  if (iDeb[node] >= l and iFin[node] <= r) {
    lazy[node] = x;
    push(node);
    return;
  }

  rangeSet(2 * node, l, r, x);
  rangeSet(2 * node + 1, l, r, x);
}

pair<int, int> rightMostBig(int node, int r, int x) {
  if (iDeb[node] > r)
    return pair(-1, -1);
  if (seg[node].first <= x)
    return pair(-1, -1);
  if (iDeb[node] == iFin[node])
    return seg[node];

  auto valR = rightMostBig(2 * node + 1, r, x);
  if (valR.first != -1)
    return valR;
  return rightMostBig(2 * node, r, x);
}

pair<int, int> leftMostBig(int node, int l, int x) {
  if (iFin[node] < l)
    return pair(-1, -1);
  if (seg[node].first <= x)
    return pair(-1, -1);
  if (iDeb[node] == iFin[node])
    return seg[node];

  auto valL = leftMostBig(2 * node, l, x);
  if (valL.first != -1)
    return valL;
  return leftMostBig(2 * node + 1, l, x);
}

int getVal(int node, int id) {
  push(node);
  if (iDeb[node] > id or iFin[node] < id)
    return -1e18;
  if (iDeb[node] == iFin[node])
    return beat[node];
  return max(getVal(2 * node, id), getVal(2 * node + 1, id));
}

int N, start;

void process(int L, int R, int side) {
  dbg(L, R, side);
  if (L == R) {
    assert(L == start);
    if (start == N - 1)
      process(L - 1, R, 0);
    else if (start == 0)
      process(L, R + 1, 1);
    if (rang[L - 1] < rang[R + 1])
      process(L - 1, R, 0);
    else
      process(L, R + 1, 1);
    return;
  }
  if (side == 0) {
    auto [val, id] = leftMostBig(1, R + 1, rang[L]);
    dbg(val, id);
    if (id == -1)
      id = N;
    if (id > R + 1)
      rangeSet(1, R + 1, id - 1, L);
    if (id < N) {
      rangeSet(1, L, L, id);
      process(L, id, 1);
    } else {
      dbg("SETL", L);
      rangeSet(1, 0, L, -1);
    }
  } else {
    auto [val, id] = rightMostBig(1, L - 1, rang[R]);
    dbg(val, id, seg[1].first);
    if (id < L - 1)
      rangeSet(1, id + 1, L - 1, R);
    if (id != -1) {
      rangeSet(1, R, R, id);
      process(id, R, 0);
    } else {
      rangeSet(1, R, N - 1, -1);
      dbg("SETR", R);
    }
  }
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> N >> start;
  --start;

  build(1, 0, N - 1);

  rang.resize(N);

  for (int &x : rang) {
    cin >> x;
  }
  dbg(rang);
  set<pair<int, int>> order;
  for (int i = 0; i < N; ++i)
    order.emplace(rang[i], i);
  for (int i = 0; i < N; ++i)
    setPos(1, i, rang[i]);

  build(1, 0, N - 1);
  process(start, start, 0);

  int nbRequetes;
  cin >> nbRequetes;

  for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) {
    char type;
    cin >> type;
    if (type == 'F') {
      int id;
      cin >> id;
      --id;
      if (id == start)
        cout << 0 << '\n';
      else {
        int iBeat = getVal(1, id);
        if (iBeat == -1) {
          if (id < start)
            cout << N - id - 1 << '\n';
          else
            cout << id << '\n';
        } else {
          if (id < start)
            cout << iBeat - id - 1 << '\n';
          else
            cout << id - iBeat - 1 << '\n';
        }
      }
    } else {
      int id, newRank;
      cin >> id >> newRank;
      --id;
      if (newRank == 1) {
        int curMax = order.rbegin()->first;
        order.erase({rang[id], id});
        rang[id] = curMax + 1;
        order.emplace(rang[id], id);
        setPos(1, id, rang[id]);
      } else {
        vector<pair<int, int>> needAddOne;
        for (int i = 0; i < newRank - 1; ++i) {
          auto [o, j] = *order.rbegin();
          order.erase({o, j});
          needAddOne.emplace_back(o, j);
        }
        for (auto [o, j] : needAddOne) {
          rang[j] = o + 1;
          setPos(1, j, rang[j]);
          order.emplace(rang[j], j);
        }
        int val = needAddOne.back().first;
        order.erase({rang[id], id});
        rang[id] = val;
        order.emplace(rang[id], id);
        setPos(1, id, rang[id]);
      }
      int iBeat = getVal(1, id);
      if (id != start and iBeat != -1) {
        if (id < start)
          process(id, iBeat - 1, 0);
        else
          process(iBeat + 1, id, 1);
      }
    }
  }
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 388 KB Output is correct
4 Correct 9 ms 460 KB Output is correct
5 Correct 26 ms 2740 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1000 ms 6964 KB Output is correct
2 Correct 550 ms 7024 KB Output is correct
3 Correct 812 ms 7036 KB Output is correct
4 Correct 456 ms 7048 KB Output is correct
5 Correct 1265 ms 9772 KB Output is correct
6 Correct 1000 ms 10180 KB Output is correct
7 Correct 1045 ms 9928 KB Output is correct
8 Correct 468 ms 10184 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 21580 KB Output is correct
2 Correct 113 ms 21440 KB Output is correct
3 Correct 86 ms 21408 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 293 ms 45796 KB Output is correct
6 Correct 265 ms 45704 KB Output is correct
7 Correct 181 ms 45100 KB Output is correct

Subtask #4
33.333333 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 1420 KB Output is correct
2 Correct 83 ms 1984 KB Output is correct
3 Correct 200 ms 11148 KB Output is correct
4 Correct 242 ms 11176 KB Output is correct
5 Correct 260 ms 2112 KB Output is correct
6 Correct 321 ms 13232 KB Output is correct
7 Correct 226 ms 4628 KB Output is correct
8 Correct 563 ms 22168 KB Output is correct
9 Correct 1968 ms 50468 KB Output is correct
10 Correct 850 ms 5572 KB Output is correct
11 Correct 1121 ms 10480 KB Output is correct
12 Execution timed out 2021 ms 46584 KB Time limit exceeded
13 Correct 1278 ms 50600 KB Output is correct