oj.uz

Submission #556051

# Submission time Handle Problem Language Result Execution time Memory
556051 2022-05-02T09:05:55 Z Bungmint Wall (IOI14_wall) C++17
100 / 100
 1345 ms 92056 KB 
// Copyright © 2022 Youngmin Park. All rights reserved.
//#pragma GCC optimize("O3")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpi = vector<pii>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
template <typename T, size_t SZ>
using ar = array<T, SZ>;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

#define all(v) (v).begin(), (v).end()
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound

constexpr int INF = 1e9;
constexpr ll LINF = 1e18;
const ld PI = acos((ld)-1.0);
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
constexpr bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
constexpr bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p)
{
	return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v)
{
	os << '{';
	string sep;
	for (const T &x : v)
		os << sep << x, sep = ", ";
	return os << '}';
}
template <typename T>
ostream &operator<<(ostream &os, const deque<T> &v) {
	os << vector<T>(all(v));
	return os;
}
template <typename T, typename S, typename C>
ostream &operator<<(ostream &os, priority_queue<T, S, C> pq) {
	vector<T> v;
	while (sz(pq)) {
		v.pb(pq.top());
		pq.pop();
	}
	os << v;
	return os;
}
void dbg_out()
{
	cerr << "\033[0m" << endl;
}
template <typename Head, typename... Tail>
void dbg_out(Head H, Tail... T)
{
	cerr << ' ' << H;
	dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr << "\033[1;35m(" << #__VA_ARGS__ << "):\033[33m", dbg_out(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

inline namespace RecursiveLambda
{
	template <typename Fun>
	struct y_combinator_result
	{
		Fun fun_;
		template <typename T>
		explicit y_combinator_result(T &&fun) : fun_(forward<T>(fun)) {}
		template <typename... Args>
		decltype(auto) operator()(Args &&...args)
		{
			return fun_(ref(*this), forward<Args>(args)...);
		}
	};
	template <typename Fun>
	decltype(auto) y_combinator(Fun &&fun)
	{
		return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
	}
};

class Range {
	struct Iter
	{
		int iter;
		constexpr Iter(int it) noexcept : iter(it) {}
		constexpr void operator++() noexcept { iter++; }
		constexpr bool operator!=(const Iter &other) const noexcept { return iter != other.iter; }
		constexpr int operator*() const noexcept { return iter; }
	};
	const Iter first, last;

public:
	explicit constexpr Range(const int f, const int l) noexcept : first(f), last(max(f, l)) {}
	constexpr Iter begin() const noexcept { return first; }
	constexpr Iter end() const noexcept { return last; }
};

constexpr Range rep(const int l, const int r) noexcept { return Range(l, r); }
constexpr Range rep(const int n) noexcept { return Range(0, n); }

class ReversedRange {
    struct Iter {
        int itr;
        constexpr Iter(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { --itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr int operator*() const noexcept { return itr; }
    };
    const Iter first, last;
 
  public:
    explicit constexpr ReversedRange(const int f, const int l) noexcept
        : first(l - 1), last(min(f, l) - 1) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};
 
constexpr ReversedRange per(const int l, const int r) noexcept { return ReversedRange(l, r); }
constexpr ReversedRange per(const int n) noexcept { return ReversedRange(0, n); }
 
/**
 * Description: Generic segment tree with lazy propagation
 * Source: Inspired by Jiangly - https://codeforces.com//contest/1672/submission/154766851
 * Verification: https://cses.fi/problemset/task/1735
 * Time Complexity: O(n) build, O(log n) per update/query
 */
template<typename T, typename U, typename Merge = plus<T>>
struct LazySegTree{
	int sz;
	const Merge merge;
	vector<T> t;
	vector<U> lazy;
	LazySegTree(int n) : merge(Merge()) {
		sz = 1;
		while (sz < n) sz *= 2;
		t.assign(sz * 2, {0, 0});
		lazy.resize(sz * 2);
	}
	void build(vector<T> &vec, int x, int l, int r)
	{
	    if (r - l == 1)
	    {
	        if (l < (int)vec.size())
	            t[x] = vec[l];
	        return;
	    }
	    int mid = (l + r) / 2;
	    build(vec, 2 * x + 1, l, mid);
	    build(vec, 2 * x + 2, mid, r);
	    t[x] = merge(t[2 * x + 1], t[2 * x + 2]);
	}
	void build(vector<T> &vec)
	{
	    build(vec, 0, 0, sz);
	}
	void upd(int i, const T& v, int x, int l, int r)
	{
	    if (r - l == 1)
	    {
	        t[x] = v;
	        return;
	    }
	    int mid = (l + r) / 2;
	    if (i < mid)
	        upd(i, v, 2 * x + 1, l, mid);
	    else
	        upd(i, v, 2 * x + 2, mid, r);
	    t[x] = merge(t[2 * x + 1], t[2 * x + 2]);
	}
	void upd(int i, const T& v)
	{
	    upd(i, v, 0, 0, sz);
	}
	void rangeUpd(int l, int r, U v, int x, int lx, int rx) {
		push(x, lx, rx);
		if (lx >= r || rx <= l) return;
		if (lx >= l && rx <= r) {
			lazy[x] = lazyOnLazy(lazy[x], v);
			push(x, lx, rx);
			return;
		}
		int mid = (lx + rx) / 2;
		rangeUpd(l, r, v, 2 * x + 1, lx, mid);
		rangeUpd(l, r, v, 2 * x + 2, mid, rx);
		t[x] = merge(t[2 * x + 1], t[2 * x + 2]);
	}
	void rangeUpd(int l, int r, U v) {
		rangeUpd(l, r, v, 0, 0, sz);
	}
	T query(int l, int r, int x, int lx, int rx)
	{
		push(x, lx, rx);
	    if (lx >= r || rx <= l)
	        return T();
	    if (lx >= l && rx <= r)
	        return t[x];
	    int mid = (lx + rx) / 2;
	    T a = query(l, r, 2 * x + 1, lx, mid);
	    T b = query(l, r, 2 * x + 2, mid, rx);
	    return merge(a, b);
	}
	T query(int l, int r)
	{
	    return query(l, r, 0, 0, sz);
	}
	void push(int x, int l, int r) {
		if (lazy[x] == U()) return;
		t[x] = lazyOnVal(t[x], lazy[x], l, r);
		if (r - l > 1) {
			lazy[2 * x + 1] = lazyOnLazy(lazy[2 * x + 1], lazy[x]);
			lazy[2 * x + 2] = lazyOnLazy(lazy[2 * x + 2], lazy[x]);
		}
		lazy[x] = U();
	}
	U lazyOnLazy(U oldV, U newV) {
		return oldV + newV;
	}
	T lazyOnVal(T val, U la, int l, int r) {
		if (la.lo >= val.ma) {
			return {la.lo, la.lo};
		}else if (la.hi <= val.mi) {
			return {la.hi, la.hi};
		}
		return {max(val.mi, la.lo), min(val.ma, la.hi)};
	}
};

struct MinMax {
	int mi, ma;
	MinMax(int mi_ = INF, int ma_ = 0) : mi(mi_), ma(ma_) {}
	MinMax operator+(const MinMax& other) const {
		return {
			min(mi, other.mi),
			max(ma, other.ma)
		};
	}
};
const MinMax ZERO = {0, 0};
struct Lazy {
	int lo, hi;
	Lazy(int lo_ = 0, int hi_ = INF) : lo(lo_), hi(hi_) {}
	Lazy operator+(const Lazy& other) const {
		if (other.lo >= hi) {
			return {other.lo, other.lo};
		}else if (other.hi <= lo) return {other.hi, other.hi};
		return {max(lo, other.lo), min(hi, other.hi)};
	}
	bool operator==(const Lazy& other) const {
		return lo == other.lo && hi == other.hi;
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
	LazySegTree<MinMax, Lazy> st(n);
	for (int i : rep(k)) {
		Lazy l{};
		if (op[i] == 1) {
			l.lo = height[i];
		}else l.hi = height[i];
		st.rangeUpd(left[i], right[i] + 1, l);
	}
	for (int i : rep(n)) {
		finalHeight[i] = st.query(i, i + 1).mi;
	}
}

// void solve()
// {
// }

// int main()
// {
// 	cin.tie(0)->sync_with_stdio(0);
// 	cin.exceptions(cin.failbit);
// 	int testcase = 1;
// 	cin >> testcase;
// 	while (testcase--)
// 	{
// 		solve();
// 	}
// #ifdef LOCAL
// 	cerr << "Time elapsed: " << 1.0 * (double)clock() / CLOCKS_PER_SEC << " s.\n";
// #endif
// }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 312 KB Output is correct
4 Correct 10 ms 980 KB Output is correct
5 Correct 7 ms 980 KB Output is correct
6 Correct 7 ms 956 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 143 ms 13876 KB Output is correct
3 Correct 248 ms 8420 KB Output is correct
4 Correct 766 ms 19940 KB Output is correct
5 Correct 360 ms 22784 KB Output is correct
6 Correct 346 ms 21220 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 16 ms 1016 KB Output is correct
5 Correct 8 ms 980 KB Output is correct
6 Correct 8 ms 1016 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 154 ms 14048 KB Output is correct
9 Correct 253 ms 8340 KB Output is correct
10 Correct 760 ms 22232 KB Output is correct
11 Correct 353 ms 22772 KB Output is correct
12 Correct 425 ms 21112 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 144 ms 13896 KB Output is correct
15 Correct 57 ms 2400 KB Output is correct
16 Correct 1051 ms 22236 KB Output is correct
17 Correct 383 ms 21652 KB Output is correct
18 Correct 343 ms 21660 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 11 ms 1012 KB Output is correct
5 Correct 7 ms 1012 KB Output is correct
6 Correct 7 ms 980 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 144 ms 13840 KB Output is correct
9 Correct 241 ms 8424 KB Output is correct
10 Correct 826 ms 22232 KB Output is correct
11 Correct 356 ms 22732 KB Output is correct
12 Correct 349 ms 21112 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 163 ms 13904 KB Output is correct
15 Correct 52 ms 2388 KB Output is correct
16 Correct 1002 ms 22216 KB Output is correct
17 Correct 371 ms 21660 KB Output is correct
18 Correct 356 ms 21664 KB Output is correct
19 Correct 1345 ms 92056 KB Output is correct
20 Correct 1307 ms 92044 KB Output is correct
21 Correct 1299 ms 91988 KB Output is correct
22 Correct 1325 ms 92044 KB Output is correct
23 Correct 1335 ms 92044 KB Output is correct
24 Correct 1334 ms 91960 KB Output is correct
25 Correct 1293 ms 92032 KB Output is correct
26 Correct 1316 ms 91952 KB Output is correct
27 Correct 1287 ms 92048 KB Output is correct
28 Correct 1203 ms 92044 KB Output is correct
29 Correct 1181 ms 92048 KB Output is correct
30 Correct 1212 ms 91996 KB Output is correct