# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
530395 | cqtshadow | Deda (COCI17_deda) | C++14 | 105 ms | 7872 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;
const int INF = (int)1e9 + 2;
class SegmentTree {
private :
int n;
vector<int> val;
void update(int pos, int l, int r, int id, int nval) {
if(r < id || id < l) return;
if(l == r) {
val[pos] = nval;
return;
}
int mid = (l + r) >> 1;
update(pos<<1, l, mid, id, nval);
update(pos<<1|1, mid + 1, r, id, nval);
val[pos] = min(val[pos<<1], val[pos<<1|1]);
}
int findSmallest(int pos, int l, int r, int u, int v, int k) {
if(v < l || r < u || r < l) return -1;
if(u <= l && r <= v) {
if(val[pos] > k) return -1;
int root = pos;
int le = l, ri = r;
while(le < ri) {
int mid = (le + ri) >> 1;
if(val[root<<1] <= k) {
ri = mid;
root = root * 2;
} else {
le = mid + 1;
root = root*2 + 1;
}
}
return le;
}
int mid = (l + r) >> 1;
int res = findSmallest(pos<<1, l, mid, u, v, k);
if(res == -1)
return findSmallest(pos<<1|1, mid + 1, r, u, v, k);
return res;
}
public :
SegmentTree(int x = 0) {
this->n = x;
if(x > 0)
val.assign(4*x + 1, INF);
}
void update(int id, int nval) {
update(1, 1, n, id, nval);
}
int findSmallest(int l, int r, int k) {
return findSmallest(1, 1, n, l, r, k);
}
};
SegmentTree myit;
int n, q, x, y;
char c;
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> q;
myit = SegmentTree(n);
while(q--) {
cin >> c >> x >> y;
if(c == 'M') myit.update(y, x);
else cout << myit.findSmallest(y, n, x) << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |