#include <bits/stdc++.h>
using namespace std;
#define MAXN 200000
#define INFTY 1e9 + 1
int n, q, tree[4*MAXN + 1];
void Build(int lo, int hi, int v) {
if (lo == hi) {
tree[v] = INFTY;
return;
}
int mid = (lo + hi)/2;
Build(lo, mid, 2*v);
Build(mid + 1, hi, 2*v + 1);
tree[v] = min(tree[2*v], tree[2*v + 1]);
}
void Update(int lo, int hi, int v, int i, int delta) {
if (lo == hi) {
tree[v] = delta;
return;
}
int mid = (lo + hi)/2;
if (i <= mid)
Update(lo, mid, 2*v, i, delta);
else
Update(mid + 1, hi, 2*v + 1, i, delta);
tree[v] = min(tree[2*v], tree[2*v + 1]);
}
int Min(int lo, int hi, int v, int l, int r) {
if (l <= lo && hi <= r)
return tree[v];
if (l > hi || r < lo)
return INFTY;
int mid = (lo + hi)/2;
int MinL = Min(lo, mid, 2*v, l, r);
int MinR = Min(mid + 1, hi, 2*v + 1, l, r);
return min(MinL, MinR);
}
/*void Query(int lo, int hi, int y) {
if (lo == hi) {
printf("%d\n", Min(1, n, 1, lo, lo) <= y ? lo : -1);
return;
}
int j = (lo + hi)/2;
if (Min(1, n, 1, lo, j) <= y)
Query(lo, j, y);
else
Query(j + 1, hi, y);
}*/
int Query(int lo, int hi, int v, int y, int b) {
if (lo == hi) {
return tree[v] <= y && lo >= b? lo : -1;
}
int mid = (lo + hi)/2;
if (tree[2*v] <= y && mid >= b) {
int q1 = Query(lo, mid, 2*v, y, b);
if (q1 == -1)
return Query(mid + 1, hi, 2*v + 1, y, b);
}
else {
return Query(mid + 1, hi, 2*v + 1, y, b);
}
}
int main() {
scanf("%d%d", &n, &q);
Build(1, n, 1);
while (q--) {
char task; int a, b; scanf(" %c%d%d", &task, &a, &b);
if (task == 'M')
Update(1, n, 1, b, --a);
else
printf("%d\n", Query(1, n, 1, a, b));
//Query(b, n, a);
}
return 0;
}
Compilation message
deda.cpp: In function 'int Query(int, int, int, int, int)':
deda.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
67 | }
| ^
deda.cpp: In function 'int main()':
deda.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
deda.cpp:73:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | char task; int a, b; scanf(" %c%d%d", &task, &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Incorrect |
5 ms |
348 KB |
Output isn't correct |
4 |
Incorrect |
371 ms |
3228 KB |
Output isn't correct |
5 |
Execution timed out |
1014 ms |
2688 KB |
Time limit exceeded |
6 |
Execution timed out |
1033 ms |
3212 KB |
Time limit exceeded |
7 |
Execution timed out |
1020 ms |
2736 KB |
Time limit exceeded |