Submission #538323

#TimeUsernameProblemLanguageResultExecution timeMemory
538323fcwWall (IOI14_wall)C++17
Compilation error
0 ms0 KiB
#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?) */

Compilation message (stderr)

/usr/bin/ld: /tmp/ccrMulXu.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccN4BBOx.o:wall.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccrMulXu.o: in function `main':
grader.cpp:(.text.startup+0x133): undefined reference to `buildWall(int, int, int*, int*, int*, int*, int*)'
collect2: error: ld returned 1 exit status