| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 538323 | fcw | Wall (IOI14_wall) | C++17 | 0 ms | 0 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>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;
template<class T> struct segtree_range {
int H, N;
vector<T> ts;
segtree_range() {}
explicit segtree_range(int N_) {
for (H = 0, N = 1; N < N_; ++H, N *= 2) {}
ts.resize(2*N);
}
template<class Q> explicit segtree_range(const vector<Q>& qs) {
const int N_ = int(qs.size());
for (H = 1, N = 1; N < N_; ++H, N *= 2) {}
ts.resize(2*N);
for (int i = 0; i < N_; ++i) at(i) = T(qs[i]);
build();
}
T& at(int a) { return ts[a + N]; }
void build() { for (int a = N; --a; ) merge(a); }
inline void push(int a) { ts[a].push(ts[2 * a], ts[2 * a + 1]); }
inline void merge(int a) { ts[a].merge(ts[2*a], ts[2*a+1]); }
void for_parents_down(int a, int b) {
for (int h = H; h; --h) {
const int l = (a >> h), r = (b >> h);
if (l == r) {
if ((l << h) != a || (r << h) != b) push(l);
} else {
if ((l << h) != a) push(l);
if ((r << h) != b) push(r);
}
}
}
void for_parents_up(int a, int b) {
for (int h = 1; h <= H; ++h) {
const int l = (a >> h), r = (b >> h);
if (l == r) {
if ((l << h) != a || (r << h) != b) merge(l);
} else {
if ((l << h) != a) merge(l);
if ((r << h) != b) merge(r);
}
}
}
template<class F, class... Args> void update(int a, int b, F f, Args&&... args) {
if (a == b) return;
a += N; b += N;
for_parents_down(a, b);
for (int l = a, r = b; l < r; l /= 2, r /= 2) {
if (l & 1) (ts[l++].*f)(args...);
if (r & 1) (ts[--r].*f)(args...);
}
for_parents_up(a, b);
}
T query(int a, int b) {
if (a == b) return T();
a += N; b += N;
for_parents_down(a, b);
T lhs, rhs, t;
for (int l = a, r = b; l < r; l /= 2, r /= 2) {
if (l & 1) { t.merge(lhs, ts[l++]); lhs = t; }
if (r & 1) { t.merge(ts[--r], rhs); rhs = t; }
}
t.merge(lhs, rhs); return t;
}
template<class Op, class E, class F, class... Args>
auto query(int a, int b, Op op, E e, F f, Args&&... args) {
if (a == b) return e();
a += N; b += N;
for_parents_down(a, b);
auto lhs = e(), rhs = e();
for (int l = a, r = b; l < r; l /= 2, r /= 2) {
if (l & 1) lhs = op(lhs, (ts[l++].*f)(args...));
if (r & 1) rhs = op((ts[--r].*f)(args...), rhs);
}
return op(lhs, rhs);
}
// find min i s.t. T::f(args...) returns true in [a, i) from left to right
template<class F, class... Args> int find_right(int a, F f, Args &&... args) {
assert(0 <= a && a <= N);
if ((T().*f)(args...)) return a;
if (a == N) return 1 + N;
a += N;
for (int h = H; h; --h) push(a >> h);
for (; ; a /= 2) if (a & 1) {
if ((ts[a].*f)(args...)) {
for (; a < N; ) {
push(a);
if (!(ts[a <<= 1].*f)(args...)) ++a;
}
return a - N + 1;
}
++a;
if (!(a & (a - 1))) return N + 1;
}
}
// find max i s.t. T::f(args...) returns true in [i, a) from right to left
template<class F, class... Args> int find_left(int a, F f, Args &&... args) {
assert(0 <= a && a <= N);
if ((T().*f)(args...)) return a;
if (a == 0) return -1;
a += N;
for (int h = H; h; --h) push((a - 1) >> h);
for (; ; a /= 2) if ((a & 1) || a == 2) {
if ((ts[a - 1].*f)(args...)) {
for (; a <= N; ) {
push(a - 1);
if (!(ts[(a <<= 1) - 1].*f)(args...)) --a;
}
return a - N - 1;
}
--a;
if (!(a & (a - 1))) return -1;
}
}
};
struct seg_node {
int mn, mx;
int lz0, lz1;
seg_node() : mn(INT_MAX), mx(INT_MIN), lz0(INT_MAX), lz1(INT_MIN) {}
void push(seg_node& l, seg_node& r) {
l.minimize(lz0);
l.maximize(lz1);
r.minimize(lz0);
r.maximize(lz1);
lz0 = INT_MAX, lz1 = INT_MIN;
}
void merge(const seg_node& l, const seg_node& r) {
mn = min(l.mn, r.mn);
mx = max(l.mx, r.mx);
}
void minimize(int val) {
mn = lz0 = min(lz0, val);
mx = lz1 = min(lz0, lz1);
}
void maximize(int val) {
mx = lz1 = max(lz1, val);
mn = lz0 = max(lz0, lz1);
}
pair<int, int> get() const { return {mx, mn}; }
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, q;
cin>>n>>q;
vector<int>a(n);
segtree_range<seg_node>seg(n);
seg.build();
for(int i=0;i<q;i++){
int op, l, r, h;
cin>>op>>l>>r>>h;
r++;
if(op == 1) seg.update(l, r, &seg_node::maximize, h);
else seg.update(l, r, &seg_node::minimize, h);
}
for(int i=0;i<n;i++){
auto ans = seg.query(i, i+1).get();
cout<<max(0, ans.st)<<"\n";
}
return 0;
}
/*
[ ]Leu o problema certo???
[ ]Ver se precisa de long long
[ ]Viu o limite dos fors (é n? é m?)
[ ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[ ]Testar sample
[ ]Testar casos de borda
[ ]1LL no 1LL << i
[ ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/