# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
475648 | Alex_tz307 | Deda (COCI17_deda) | C++17 | 230 ms | 7236 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
struct SegTree {
int Size;
vector<int> tree;
SegTree(int n) {
Size = 1;
while (Size < n) {
Size <<= 1;
}
tree.resize(Size << 1, INF);
}
void update(int x, int lx, int rx, int pos, int val) {
if (lx == rx) {
tree[x] = val;
cout << lx << ' ' << pos << ' ' << val << endl;
return;
}
int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1;
if (pos <= mid) {
update(lSon, lx, mid, pos, val);
} else {
update(rSon, mid + 1, rx, pos, val);
}
tree[x] = min(tree[lSon], tree[rSon]);
}
int query(int x, int lx, int rx, int pos, int val) {
if (lx == rx) {
return lx;
}
int mid = (lx + rx) >> 1, lSon = x << 1, rSon = x << 1 | 1, ans = -1;
if (pos <= mid && tree[lSon] <= val) {
ans = query(lSon, lx, mid, pos, val);
}
if (ans == -1 && tree[rSon] <= val) {
return query(rSon, mid + 1, rx, pos, val);
}
return ans;
}
};
void test_case() {
int n, q;
cin >> n >> q;
SegTree tree(n);
for (int i = 1; i <= q; ++i) {
char op;
int x, pos;
cin >> op >> x >> pos;
if (op == 'M') {
tree.update(1, 1, n, pos, x);
} else {
cout << tree.query(1, 1, n, pos, x) << '\n';
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
for (int tc = 1; tc <= T; ++tc) {
test_case();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |