Submission #44295

#TimeUsernameProblemLanguageResultExecution timeMemory
44295JustInCaseDeda (COCI17_deda)C++17
140 / 140
229 ms17224 KiB
#include <bits/stdc++.h> #define endl '\n' using namespace std; const int32_t MAX_N = 2e5 + 5; const int32_t INF = 1e9 + 5; class SegmentTree { private: int32_t treeSize, data[4 * MAX_N]; void Build(int32_t node, int32_t low, int32_t high) { if(low == high) { data[node] = INF; return; } int32_t mid = (low + high) / 2; Build(2 * node, low, mid); Build(2 * node + 1, mid + 1, high); data[node] = min(data[2 * node], data[2 * node + 1]); } void Update(int32_t node, int32_t low, int32_t high, int32_t qInd, int32_t qVal) { if(low > qInd || high < qInd) { return; } else if(low == qInd && high == qInd) { data[node] = qVal; return; } int32_t mid = (low + high) / 2; Update(2 * node, low, mid, qInd, qVal); Update(2 * node + 1, mid + 1, high, qInd, qVal); data[node] = min(data[2 * node], data[2 * node + 1]); } int32_t Query(int32_t node, int32_t low, int32_t high, int32_t qLow, int32_t qVal) { if(high < qLow || data[node] > qVal) { return -1; } else if(low == high) { if(data[node] <= qVal) { return low; } else { return -1; } } int32_t mid = (low + high) / 2; int32_t ansLeft = Query(2 * node, low, mid, qLow, qVal); if(ansLeft != -1) { return ansLeft; } return Query(2 * node + 1, mid + 1, high, qLow, qVal); } public: void Init(int32_t n) { treeSize = n; Build(1, 1, treeSize); } void Update(int32_t ind, int32_t val) { Update(1, 1, treeSize, ind, val); } int32_t Query(int32_t low, int32_t val) { return Query(1, 1, treeSize, low, val); } }; SegmentTree segTree; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int32_t n, q; cin >> n >> q; segTree.Init(n); for(int32_t i = 1; i <= q; i++) { char type; cin >> type; if(type == 'M') { int32_t x, a; cin >> x >> a; segTree.Update(a, x); } else { int32_t y, b; cin >> y >> b; cout << segTree.Query(b, y) << endl; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...