# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
909913 | crafticat | Deda (COCI17_deda) | C++17 | 419 ms | 23668 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>
using namespace std;
constexpr int inf = 1e9 + 7;
struct Segment {
Segment *left = nullptr, *right = nullptr;
int minY = inf;
int l, r, mid;
Segment(int l, int r) : l(l), r(r), mid((l + r) / 2) {
if (r - 1 > l) {
left = new Segment(l,mid);
right = new Segment(mid,r);
}
}
void checkForUpdates() {
minY = min(left->minY,right->minY);
}
void update(int x, int u) {
if (r - 1 <= l) {
minY = u;
return;
}
if (x >= mid) {
right->update(x,u);
} else {
left->update(x,u);
}
checkForUpdates();
}
int get(int a, int b, int k) {
// Fully in
if (a <= l && b >= r) {
//return l;
}
// Fully out
if (a >= r || b <= l) {
return inf;
}
if (minY > k) return inf;
if (r - 1 <= l) {
if (minY > k) return inf;
return l;
}
if (left->minY <= k) {
int v = left->get(a,b,k);
if (v == inf) return right->get(a,b,k);
return v;
}
else
return right->get(a,b,k);
}
};
int main() {
int n, m; cin >> n >> m;
Segment seg(0,n + 1);
for (int i = 0; i < m; i++) {
char t; cin >> t;
if (t == 'M') {
int a, b; cin >> a >> b;
seg.update(b,a);
} else {
int a, b; cin >> a >> b;
int v = seg.get(b,n,a);
if (v == inf) v = -1;
cout << v << "\n";
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |