oj.uz

답안 #680597

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680597 2023-01-11T10:33:15 Z peijar 케이크 (CEOI14_cake) C++17
100 / 100
 1477 ms 36492 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);
  priority_queue<pair<int, int>> pq;
  set<pair<int, int>> order;
  for (int i = 0; i < N; ++i)
    pq.emplace(rang[i], i);

  auto getPq = [&]() {
    while (true) {
      auto [r, i] = pq.top();
      pq.pop();
      if (r != rang[i])
        continue;
      return pair(r, 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) {
        auto [curMax, idMax] = getPq();
        pq.emplace(curMax, idMax);
        rang[id] = curMax + 1;
        pq.emplace(rang[id], id);
        setPos(1, id, rang[id]);
      } else {
        vector<pair<int, int>> needAddOne;
        for (int i = 0; i < newRank - 1; ++i) {
          needAddOne.push_back(getPq());
        }
        for (auto [o, j] : needAddOne) {
          rang[j] = o + 1;
          setPos(1, j, rang[j]);
          pq.emplace(rang[j], j);
        }
        int val = needAddOne.back().first;
        rang[id] = val;
        pq.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 0 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 12 ms 596 KB Output is correct
5 Correct 33 ms 2368 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 816 ms 6156 KB Output is correct
2 Correct 565 ms 10260 KB Output is correct
3 Correct 721 ms 10208 KB Output is correct
4 Correct 425 ms 10300 KB Output is correct
5 Correct 1027 ms 11900 KB Output is correct
6 Correct 914 ms 7856 KB Output is correct
7 Correct 895 ms 20096 KB Output is correct
8 Correct 447 ms 20200 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 15688 KB Output is correct
2 Correct 93 ms 15564 KB Output is correct
3 Correct 73 ms 15472 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 216 ms 31616 KB Output is correct
6 Correct 138 ms 31588 KB Output is correct
7 Correct 127 ms 31064 KB Output is correct

Subtask #4
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 1460 KB Output is correct
2 Correct 67 ms 1828 KB Output is correct
3 Correct 174 ms 9160 KB Output is correct
4 Correct 182 ms 9084 KB Output is correct
5 Correct 238 ms 3000 KB Output is correct
6 Correct 216 ms 11552 KB Output is correct
7 Correct 228 ms 4352 KB Output is correct
8 Correct 472 ms 21728 KB Output is correct
9 Correct 1477 ms 36492 KB Output is correct
10 Correct 723 ms 5624 KB Output is correct
11 Correct 903 ms 13264 KB Output is correct
12 Correct 1401 ms 35308 KB Output is correct
13 Correct 1006 ms 35804 KB Output is correct