/**
* ┏┓ ┏┓
* ┏┛┗━━━━━━━┛┗━━━┓
* ┃ ┃
* ┃ ━ ┃
* ┃ ＞ ＜ ┃
* ┃ ┃
* ┃... ⌒ ... ┃
* ┃ ┃
* ┗━┓ ┏━┛
* ┃ ┃ Code is far away from bug with the animal protecting
* ┃ ┃ 神兽保佑,代码无bug
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┃
* ┃ ┗━━━┓
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━━━━━━━━┳┓┏┛
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛
*/
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int long long
#define cl(x) (x << 1)
#define cr(x) (x << 1) + 1
const int INF = 1e17;
int ans = 1e18;
struct node {
int val;
};
struct SEG {
int n;
vector<node> seg;
vector<node> arr;
void init(int a) {
n = a;
seg.resize(4 * n + 5);
arr.resize(a + 1);
}
void pull(int id) {
auto a = seg[cl(id)];
auto b = seg[cr(id)];
seg[id] = {min(a.val, b.val)};
}
void build(int id, int l, int r) {
if (l == r) {
seg[id] = arr[l];
return;
}
int mid = (l + r) >> 1;
build(cl(id), l, mid);
build(cr(id), mid + 1, r);
pull(id);
}
void update(int id, int l, int r, int x, int v) {
if (l == r) {
seg[id] = {v};
return;
}
int mid = (l + r) >> 1;
if (x <= mid) {
update(cl(id), l, mid, x, v);
}
if (mid < x) {
update(cr(id), mid + 1, r, x, v);
}
pull(id);
}
node query(int id, int l, int r, int sl, int sr) {
if (sl <= l && r <= sr) { // 目前這個區間在查詢區間內
return seg[id];
}
int mid = (l + r) >> 1;
node ans1, ans2;
bool f1 = 0, f2 = 0;
if (sl <= mid) { // 左區間跟查詢區間有交集
ans1 = query(cl(id), l, mid, sl, sr);
f1 = 1;
}
if (mid < sr) { // 右區間跟查詢區間有交集
ans2 = query(cr(id), mid + 1, r, sl, sr);
f2 = 1;
}
if (f1 && f2) {
return {min(ans1.val, ans2.val)};
}
if (f1) return ans1;
if (f2) return ans2;
}
int fquery(int l, int r, int v) {
int p = query(1, 1, n, l, r).val;
if (p > v) return -1;
while (l != r) {
int mid = (l + r) >> 1;
int x = query(1, 1, n, l, mid).val;
if (x <= v)
r = mid;
else
l = mid + 1;
}
return l;
}
int xxxquery(int id, int l, int r, int sl, int sr, int tag) {
if (sl <= l && r <= sr) { // 目前這個區間在查詢區間內
if (seg[id].val > tag) return seg[id].val;
if (l == r) {
ans = min(ans, l);
return seg[id].val;
}
}
int mid = (l + r) >> 1;
int ans1, ans2;
bool f1 = 0, f2 = 0;
if (sl <= mid) { // 左區間跟查詢區間有交集
ans1 = xxxquery(cl(id), l, mid, sl, sr, tag);
f1 = 1;
if (ans1 < tag) return ans1;
}
if (mid < sr) { // 右區間跟查詢區間有交集
ans2 = xxxquery(cr(id), mid + 1, r, sl, sr, tag);
f2 = 1;
}
if (f1 && f2) {
return min(ans1, ans2);
}
if (f1) return ans1;
if (f2) return ans2;
}
} tree;
signed main() {
FASTIO;
int n, q;
cin >> n >> q;
tree.init(n);
for (int i = 1; i <= n; i++)
tree.arr[i] = {INF};
tree.build(1, 1, n);
for (int i = 0; i < q; i++) {
char sta;
int x, a, y, b;
cin >> sta;
if (sta == 'M') {
cin >> x >> a;
tree.update(1, 1, n, a, x);
}
if (sta == 'D') {
cin >> y >> b;
ans = 1e18;
tree.xxxquery(1, 1, n, b, n, y);
if (ans == 1e18) ans = -1;
cout << ans << '\n';
}
}
}
Compilation message
deda.cpp: In member function 'long long int SEG::xxxquery(long long int, long long int, long long int, long long int, long long int, long long int)':
deda.cpp:135:5: warning: control reaches end of non-void function [-Wreturn-type]
135 | }
| ^
deda.cpp: In function 'int main()':
deda.cpp:119:13: warning: 'ans1' may be used uninitialized in this function [-Wmaybe-uninitialized]
119 | int ans1, ans2;
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
348 KB |
Output is correct |
| 4 |
Correct |
96 ms |
9216 KB |
Output is correct |
| 5 |
Correct |
82 ms |
7504 KB |
Output is correct |
| 6 |
Correct |
84 ms |
9556 KB |
Output is correct |
| 7 |
Correct |
86 ms |
11616 KB |
Output is correct |
