# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
136846 | KCSC | Deda (COCI17_deda) | C++14 | 868 ms | 8080 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 DIM = 200005;
const int INF = 0x3f3f3f3f;
int sgt[DIM * 4];
void update(int nd, int le, int ri, int ps, int vl) {
if (le == ri)
sgt[nd] = vl;
else {
int md = (le + ri) / 2;
if (ps <= md)
update(nd * 2, le, md, ps, vl);
else
update(nd * 2 + 1, md + 1, ri, ps, vl);
sgt[nd] = min(sgt[nd * 2], sgt[nd * 2 + 1]);
}
}
int query2(int nd, int le, int ri, int vl) {
if (sgt[nd] > vl)
return INF;
if (le == ri)
return le;
else {
int md = (le + ri) / 2;
int val = query2(nd * 2, le, md, vl);
if (val == INF)
val = query2(nd * 2 + 1, md + 1, ri, vl);
return val;
}
}
int query(int nd, int le, int ri, int st, int en, int vl) {
if (en < le || ri < st || sgt[nd] > vl)
return INF;
if (st <= le && ri <= en)
return query2(nd, le, ri, vl);
else {
int md = (le + ri) / 2;
int val = query(nd * 2, le, md, st, en, vl);
if (val == INF)
val = query(nd * 2 + 1, md + 1, ri, st, en, vl);
return val;
}
}
int main(void) {
// freopen("deda.in", "r", stdin);
// freopen("deda.out", "w", stdout);
int n, q;
cin >> n >> q;
memset(sgt, INF, sizeof sgt);
for (int i = 1; i <= q; ++i) {
char t; int a, b;
cin >> t >> a >> b;
if (t == 'M')
update(1, 1, n, b, a);
else {
int val = query(1, 1, n, b, n, a);
if (val == INF)
val = -1;
cout << val << "\n";
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |