oj.uz

Submission #105059

# Submission time Handle Problem Language Result Execution time Memory
105059 2019-04-10T11:35:20 Z WLZ Cake (CEOI14_cake) C++17
100 / 100
 1157 ms 51964 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int n, a;
vector<int> d, top10;

struct node {
  int i, j;
  node *left, *right;
  int val;
};

node* build(int i, int j) {
  if (i == j) {
    return new node{i, j, nullptr, nullptr, 0};
  }
  node* left = build(i, (i + j) / 2);
  node* right = build((i + j) / 2 + 1, j);
  return new node{i, j, left, right, max(left->val, right->val)};
}

int query_mx(node* cur, int i, int j) {
  if (cur->i > j || cur->j < i) {
    return -INF;
  }
  if (cur->i >= i && cur->j <= j) {
    return cur->val;
  }
  return max(query_mx(cur->left, i, j), query_mx(cur->right, i, j));
}

void update(node* cur, int i, int newVal) {
  if (cur->i > i || cur->j < i) {
    return;
  }
  if (cur->i == i && cur->j == i) {
    cur->val = newVal;
    return;
  }
  update(cur->left, i, newVal);
  update(cur->right, i, newVal);
  cur->val = max(cur->right->val, cur->left->val);
}

int find(node* cur, int val, int dir) {
  if (cur->i == cur->j) {
    if (dir) {
      return cur->i + (cur->val < val);
    } else {
      return cur->i - (cur->val < val);
    }
  }
  if (dir) {
    if (cur->left->val < val) {
      return find(cur->right, val, dir);
    }
    return find(cur->left, val, dir);
  } else {
    if (cur->right->val < val) {
      return find(cur->left, val, dir);
    }
    return find(cur->right, val, dir);
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> a;
  d.resize(n + 1);
  node* rootl = build(1, n);
  node* rootr = build(1, n);
  for (int i = 1; i <= n; i++) {
    cin >> d[i];
    if (i < a) {
      update(rootl, i, d[i]);
    } else if (i > a) {
      update(rootr, i, d[i]);
    }
    top10.push_back(i);
  }
  sort(top10.begin(), top10.end(), [](const int& a, const int& b) {
    return d[a] > d[b];
  });
  while ((int) top10.size() > 10) {
    top10.pop_back();
  }
  int q;
  cin >> q;
  while (q--) {
    char t;
    cin >> t;
    if (t == 'E') {
      int i, e;
      cin >> i >> e;
      e--;
      for (auto it = top10.begin(); it != top10.end(); it++) {
        if (*it == i) {
          top10.erase(it);
          break;
        }
      }
      for (int j = 0; j < e; j++) {
        d[top10[j]]++;
        if (top10[j] < a) {
          update(rootl, top10[j], d[top10[j]]);
        } else if (top10[j] > a) {
          update(rootr, top10[j], d[top10[j]]);
        }
      }
      d[i] = d[top10[e]] + 1;
      top10.insert(top10.begin() + e, i);
      while ((int) top10.size() > 10) {
        top10.pop_back();
      }
      if (i < a) {
        update(rootl, i, d[i]);
      } else if (i > a) {
        update(rootr, i, d[i]);
      }
    } else {
      int b;
      cin >> b;
      if (b < a) {
        cout << find(rootr, query_mx(rootl, b, a - 1), 1) - b - 1;
      } else if (b > a) {
        cout << b - 1 - find(rootl, query_mx(rootr, a + 1, b), 0);
      } else {
        cout << 0;
      }
      cout << '\n';
    }
  }
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 7 ms 640 KB Output is correct
5 Correct 18 ms 2560 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 3340 KB Output is correct
2 Correct 166 ms 3684 KB Output is correct
3 Correct 263 ms 3576 KB Output is correct
4 Correct 165 ms 3576 KB Output is correct
5 Correct 393 ms 6520 KB Output is correct
6 Correct 304 ms 6644 KB Output is correct
7 Correct 347 ms 6744 KB Output is correct
8 Correct 195 ms 6592 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 21456 KB Output is correct
2 Correct 140 ms 21108 KB Output is correct
3 Correct 124 ms 21188 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 330 ms 50900 KB Output is correct
6 Correct 264 ms 50744 KB Output is correct
7 Correct 213 ms 50516 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1408 KB Output is correct
2 Correct 33 ms 1920 KB Output is correct
3 Correct 121 ms 11144 KB Output is correct
4 Correct 140 ms 11008 KB Output is correct
5 Correct 95 ms 1736 KB Output is correct
6 Correct 227 ms 14452 KB Output is correct
7 Correct 138 ms 3448 KB Output is correct
8 Correct 257 ms 20856 KB Output is correct
9 Correct 1144 ms 51964 KB Output is correct
10 Correct 320 ms 2544 KB Output is correct
11 Correct 443 ms 6520 KB Output is correct
12 Correct 1157 ms 41960 KB Output is correct
13 Correct 761 ms 51740 KB Output is correct