This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_D
#include "../DualSegtree.cpp"
int op(int a, int b) { return (b == -1 ? a : b); }
int e() { return -1; }
int main() {
int n, q;
cin >> n >> q;
dual_segtree<int, op, e> seg(vector<int>(n, INT_MAX));
while (q--) {
int type;
cin >> type;
if (type == 0) {
int s, t, x;
cin >> s >> t >> x;
seg.apply(s, t + 1, x);
} else {
int k;
cin >> k;
cout << seg.get(k) << endl;
}
}
}
#line 1 "test/DualSegtree.test.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_D
#line 1 "DualSegtree.cpp"
#include <bits/stdc++.h>
using namespace std;
template <class S, S (*op)(S, S), S (*e)()>
struct dual_segtree {
int sz = 1, log = 0;
vector<S> lz;
dual_segtree() = default;
dual_segtree(int n) : dual_segtree(vector<S>(n, e())) {}
dual_segtree(vector<S> a) {
int n = a.size();
while (sz < n) {
sz <<= 1;
log++;
}
lz.assign(sz << 1, e());
for (int i = 0; i < n; i++) lz[i + sz] = a[i];
}
void push(int k) {
int b = __builtin_ctz(k);
for (int d = log; d > b; d--) {
lz[k >> d << 1] = op(lz[k >> d << 1], lz[k >> d]);
lz[k >> d << 1 | 1] = op(lz[k >> d << 1 | 1], lz[k >> d]);
lz[k >> d] = e();
}
}
void apply(int l, int r, S x) {
l += sz, r += sz;
push(l);
push(r);
while (l < r) {
if (l & 1) {
lz[l] = op(lz[l], x);
l++;
}
if (r & 1) {
r--;
lz[r] = op(lz[r], x);
}
l >>= 1, r >>= 1;
}
}
S get(int k) {
k += sz;
S res = e();
while (k) {
res = op(res, lz[k]);
k >>= 1;
}
return res;
}
};
#line 3 "test/DualSegtree.test.cpp"
int op(int a, int b) { return (b == -1 ? a : b); }
int e() { return -1; }
int main() {
int n, q;
cin >> n >> q;
dual_segtree<int, op, e> seg(vector<int>(n, INT_MAX));
while (q--) {
int type;
cin >> type;
if (type == 0) {
int s, t, x;
cin >> s >> t >> x;
seg.apply(s, t + 1, x);
} else {
int k;
cin >> k;
cout << seg.get(k) << endl;
}
}
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | 00_sample_00.in |
![]() |
5 ms | 4 MB |
g++ | 00_sample_01.in |
![]() |
4 ms | 4 MB |
g++ | 01_rand_00.in |
![]() |
4 ms | 4 MB |
g++ | 01_rand_01.in |
![]() |
4 ms | 4 MB |
g++ | 01_rand_02.in |
![]() |
4 ms | 4 MB |
g++ | 01_rand_03.in |
![]() |
5 ms | 3 MB |
g++ | 01_rand_04.in |
![]() |
6 ms | 3 MB |
g++ | 01_rand_05.in |
![]() |
13 ms | 4 MB |
g++ | 02_corner_00.in |
![]() |
5 ms | 3 MB |
g++ | 02_corner_01.in |
![]() |
4 ms | 4 MB |
g++ | 03_large_00.in |
![]() |
14 ms | 4 MB |
g++ | 03_large_01.in |
![]() |
16 ms | 4 MB |
g++ | 03_large_02.in |
![]() |
15 ms | 4 MB |
g++ | 03_large_03.in |
![]() |
16 ms | 4 MB |
g++ | 04_maximum_00.in |
![]() |
108 ms | 5 MB |
g++ | 04_maximum_01.in |
![]() |
121 ms | 5 MB |
g++ | 04_maximum_02.in |
![]() |
107 ms | 5 MB |
g++ | 04_maximum_03.in |
![]() |
128 ms | 5 MB |
g++ | 05_critical_00.in |
![]() |
102 ms | 5 MB |
g++ | 05_critical_01.in |
![]() |
119 ms | 5 MB |
g++ | 05_critical_02.in |
![]() |
68 ms | 5 MB |
g++ | 05_critical_03.in |
![]() |
70 ms | 5 MB |
clang++ | 00_sample_00.in |
![]() |
5 ms | 3 MB |
clang++ | 00_sample_01.in |
![]() |
4 ms | 3 MB |
clang++ | 01_rand_00.in |
![]() |
4 ms | 4 MB |
clang++ | 01_rand_01.in |
![]() |
4 ms | 4 MB |
clang++ | 01_rand_02.in |
![]() |
4 ms | 3 MB |
clang++ | 01_rand_03.in |
![]() |
5 ms | 4 MB |
clang++ | 01_rand_04.in |
![]() |
8 ms | 4 MB |
clang++ | 01_rand_05.in |
![]() |
20 ms | 3 MB |
clang++ | 02_corner_00.in |
![]() |
4 ms | 4 MB |
clang++ | 02_corner_01.in |
![]() |
4 ms | 3 MB |
clang++ | 03_large_00.in |
![]() |
19 ms | 4 MB |
clang++ | 03_large_01.in |
![]() |
16 ms | 4 MB |
clang++ | 03_large_02.in |
![]() |
15 ms | 4 MB |
clang++ | 03_large_03.in |
![]() |
17 ms | 4 MB |
clang++ | 04_maximum_00.in |
![]() |
117 ms | 5 MB |
clang++ | 04_maximum_01.in |
![]() |
105 ms | 5 MB |
clang++ | 04_maximum_02.in |
![]() |
148 ms | 5 MB |
clang++ | 04_maximum_03.in |
![]() |
119 ms | 5 MB |
clang++ | 05_critical_00.in |
![]() |
108 ms | 5 MB |
clang++ | 05_critical_01.in |
![]() |
122 ms | 5 MB |
clang++ | 05_critical_02.in |
![]() |
68 ms | 5 MB |
clang++ | 05_critical_03.in |
![]() |
70 ms | 5 MB |