#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair <int, int> pi; //Station, child
struct node { // Creates a struct for the node of a seg tree
int s, e, m;
pi v; // start, end, middle, rangemin value
node *l, *r; // pointer to left, right subnodes
node(int _s, int _e) { //Constructor to create nodes l and r
s = _s; e = _e; m = (s+e)/2; // initialize variables
v.second = INT_MAX;
v.first = INT_MAX;
if (s!=e) { // is not a leaf node
l = new node(s, m); // create child nodes
r = new node(m+1, e);
}
}
void up(int x, int nv) { //update position x to nv (new value)
if (s==e) { //if node is a leaf, just modify v.
v = pi(nv, x);
return;
}
if (x>m) r->up(x, nv); //update right subtree if update is in right subtree
if (x<=m) l->up(x, nv); //update left subtree if update is in left subtree
v = min(l->v, r->v); //Modify the value of v after updating children
}
pi rmq(int x, int y) { //range min query from position x, y
if (s==x && e==y) return v; //return range min if query range corresponds
if (x>m) return r->rmq(x, y); //query right tree if range only lies there
if (y<=m) return l->rmq(x, y); //query left tree if range only lies there
return min(l->rmq(x, m), r->rmq(m+1, y)); //minimum of both queries as range spans both trees
}
} *root; // declares root as a pointer node. Root is the name of the segment tree.
int n, q, a, b;
char x;
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
root = new node(1, n);
for (int i = 0; i < q; i++) {
cin >> x >> a >> b;
if (x == 'M') root -> up(b, a);
else {
int counter = 0;
int c;
pi cur, previ;
c = n;
while (true) {
counter++;
cur = root -> rmq(b, c);
if (cur.first > a && counter == 1) {
cout << -1 << "\n";
break;
} else if (cur.second == b && cur.first <= a) {
cout << cur.second << "\n";
break;
} else if (cur.first > a) {
cout << previ.second << "\n";
break;
}
previ = cur;
c = cur.second - 1;
}
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
512 KB |
Output is correct |
| 4 |
Correct |
325 ms |
26496 KB |
Output is correct |
| 5 |
Correct |
418 ms |
13688 KB |
Output is correct |
| 6 |
Correct |
490 ms |
20088 KB |
Output is correct |
| 7 |
Correct |
585 ms |
26360 KB |
Output is correct |
