1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
| #pragma G++ optimize("O3")
#include <algorithm> #include <cmath> #include <cstdio> #include <ctime> #include <cstring> #include <iostream> #include <queue> #include <map> #include <set> #include <string> #include <list> #include <forward_list> #include <stack> #include <unordered_set> #include <vector> #include <limits.h>
using namespace std; const long long MAX = 2e6 + 7;
int h[MAX];
struct Node { int left, right; int max; bool empty; Node *leftSon; Node *rightSon; Node *father; };
Node &buildTree(int left, int right, Node *father = nullptr) { auto &node = *(new Node[1]); node.left = left; node.right = right; node.father = father; node.empty = false; if (left == right) { node.max = h[left]; return node; } int mid = (left + right) / 2; node.leftSon = &buildTree(left, mid, &node); node.rightSon = &buildTree(mid + 1, right, &node); node.max = max(node.leftSon->max, node.rightSon->max); return node; }
void updateFatherMax(Node &node) { int newMax = max(node.leftSon->max, node.rightSon->max); if (newMax != node.max) { node.max = newMax; if (node.father != nullptr) { updateFatherMax(*node.father); } } }
int queryMax(int left, int right, int t, Node &node) { if (node.empty || node.max < t) { return -1; } if (node.left == node.right) { node.empty = true; updateFatherMax(*node.father); return node.left; } int leftAns = -1; if (left <= node.left && right >= node.right) { leftAns = queryMax(left, right, t, *node.leftSon); return leftAns != -1 ? leftAns : queryMax(left, right, t, *node.rightSon); } int mid = (node.left + node.right) / 2; if (left <= mid) { leftAns = queryMax(left, right, t, *node.leftSon); if (leftAns != -1) { return leftAns; } } if (right > mid) { return queryMax(left, right, t, *node.rightSon); } return -1; }
int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int n, m; cin >> n; for (int i = 1; i <= n; i++) { cin >> h[i]; } auto root = buildTree(1, n); cin >> m; int s, t; int grow = 0; while (m--) { cin >> s >> t; int ans = -1; ans = queryMax(s + 1, n, t - grow, root); if (ans != -1) { ans = ans - s - 1; } else if (s != 0) { ans = queryMax(1, s, t - grow, root); if (ans != -1) { ans = (n - s - 1) + ans; } } cout << ans << " "; grow += 1; } return 0; }
|