oj.uz

Submission #485586

# Submission time Handle Problem Language Result Execution time Memory
485586 2021-11-08T12:12:22 Z cheissmart Bitaro, who Leaps through Time (JOI19_timeleap) C++14
0 / 100
 560 ms 117676 KB 
#include <bits/stdc++.h>
#define int ll
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7, N = 3e5 + 7;

int n, q;
struct DS {
	struct node {
		int l, r, x, y;
		ll cost;
		bool type; //0: only l, r
		node(int _l = 0, int _r = 0) {
			l = _l, r = _r;
			x = y = 0, type = 0, cost = 0;
		}
		pair<int, ll> eval(int pos) {
			ll ans = 0;
			int pre = pos;
			pos = max(pos, l), pos = min(pos, r);
			ans += max<ll>(0, pre - pos);
			if(type) {
				ans += cost;
				pre = pos, pos = x;
				ans += max<ll>(0, pre - pos);
				pos = y;
			}
			return {pos, ans};
		}
		friend node operator + (node lhs, node rhs) {
			node res;
			if(lhs.type) { 
				res.l = lhs.l, res.r = lhs.r, res.x = lhs.x, res.type = 1;
				auto [pos, cost] = rhs.eval(lhs.y);
				res.cost = lhs.cost + cost;
				res.y = pos;
			} else {
				if(max(lhs.l, rhs.l) < min(lhs.r, rhs.r)) {
					res = rhs;
					res.l = max(lhs.l, rhs.l);
					res.r = min(lhs.r, rhs.r);
				} else {
					res.l = lhs.l, res.r = lhs.r, res.type = 1;
					if(rhs.l >= lhs.r) {
						res.x = rhs.l;
					} else {
						res.x = rhs.r;
					}
					tie(res.y, res.cost) = rhs.eval(res.x);
				}
			}
			return res;
		}
	} t[N * 4];
	void upd(int pos, node x, int v = 1, int tl = 0, int tr = n) {
		if(tr - tl == 1) {
			assert(pos == tl);
			t[v] = x;
			return;
		}
		int tm = (tl + tr) / 2;
		if(pos < tm)
			upd(pos, x, v * 2, tl, tm);
		else
			upd(pos, x, v * 2 + 1, tm, tr);
		t[v] = t[v * 2] + t[v * 2 + 1];
	}
	void upd(int i, int l, int r) {
		l -= i, r -= i;
		upd(i, node(l, r));
	}
	node qry(int l, int r, int v = 1, int tl = 0, int tr = n) {
		if(l <= tl && tr <= r)
			return t[v];
		int tm = (tl + tr) / 2;
		if(r <= tm)
			return qry(l, r, v * 2, tl, tm);
		else if(l >= tm)
			return qry(l, r, v * 2 + 1, tm, tr);
		else
			return qry(l, r, v * 2, tl, tm) + qry(l, r, v * 2 + 1, tm, tr);
	}
} t1, t2;

signed main()
{
	IO_OP;

	cin >> n >> q;
	for(int i = 0; i < n - 1; i++) {
		int l, r;
		cin >> l >> r;
		r--;
		t1.upd(i, l, r);
		t2.upd(n - i - 1, l, r);
	}

	while(q--) {
		int op;
		cin >> op;
		if(op == 1) {
			int p, l, r;
			cin >> p >> l >> r;
			r--;
			p--;
			t1.upd(p, l, r);
			t2.upd(n - p - 1, l, r);
		} else {
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			a--, c--;
			if(a == c) {
				cout << max<ll>(b - d, 0) << '\n';
			} else if(a < c) {
				b -= a, d -= c;
				auto u = t1.qry(a, c);
				auto [pos, cost] = u.eval(b);
				cost += max<ll>(pos - d, 0);
				cout << cost << '\n';
			} else { // a > c
				a--;
				a = n - a - 1, c = n - c - 1;
				c++;
				b -= a, d -= c;
				auto u = t2.qry(a, c);
				auto [pos, cost] = u.eval(b);
				cost += max<ll>(pos - d, 0);
				cout << cost << '\n';
			}
		}
	}

}

Compilation message

timeleap.cpp: In function 'DS::node operator+(DS::node, DS::node)':
timeleap.cpp:60:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     auto [pos, cost] = rhs.eval(lhs.y);
      |          ^
timeleap.cpp: In function 'int main()':
timeleap.cpp:143:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  143 |     auto [pos, cost] = u.eval(b);
      |          ^
timeleap.cpp:152:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  152 |     auto [pos, cost] = u.eval(b);
      |          ^

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 112916 KB Output is correct
2 Correct 42 ms 112964 KB Output is correct
3 Correct 43 ms 112964 KB Output is correct
4 Correct 42 ms 112972 KB Output is correct
5 Correct 42 ms 112968 KB Output is correct
6 Correct 41 ms 112916 KB Output is correct
7 Correct 42 ms 113008 KB Output is correct
8 Correct 43 ms 112904 KB Output is correct
9 Correct 44 ms 113016 KB Output is correct
10 Correct 45 ms 113096 KB Output is correct
11 Correct 43 ms 112964 KB Output is correct
12 Correct 43 ms 113012 KB Output is correct
13 Correct 43 ms 113100 KB Output is correct
14 Correct 43 ms 113052 KB Output is correct
15 Correct 43 ms 112956 KB Output is correct
16 Correct 44 ms 113076 KB Output is correct
17 Correct 43 ms 112992 KB Output is correct
18 Correct 43 ms 112972 KB Output is correct
19 Correct 43 ms 112972 KB Output is correct
20 Correct 43 ms 113044 KB Output is correct
21 Incorrect 44 ms 113040 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 117552 KB Output is correct
2 Correct 534 ms 117676 KB Output is correct
3 Correct 555 ms 117644 KB Output is correct
4 Correct 546 ms 117628 KB Output is correct
5 Correct 542 ms 117384 KB Output is correct
6 Correct 542 ms 117412 KB Output is correct
7 Incorrect 560 ms 117504 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 112916 KB Output is correct
2 Correct 42 ms 112964 KB Output is correct
3 Correct 43 ms 112964 KB Output is correct
4 Correct 42 ms 112972 KB Output is correct
5 Correct 42 ms 112968 KB Output is correct
6 Correct 41 ms 112916 KB Output is correct
7 Correct 42 ms 113008 KB Output is correct
8 Correct 43 ms 112904 KB Output is correct
9 Correct 44 ms 113016 KB Output is correct
10 Correct 45 ms 113096 KB Output is correct
11 Correct 43 ms 112964 KB Output is correct
12 Correct 43 ms 113012 KB Output is correct
13 Correct 43 ms 113100 KB Output is correct
14 Correct 43 ms 113052 KB Output is correct
15 Correct 43 ms 112956 KB Output is correct
16 Correct 44 ms 113076 KB Output is correct
17 Correct 43 ms 112992 KB Output is correct
18 Correct 43 ms 112972 KB Output is correct
19 Correct 43 ms 112972 KB Output is correct
20 Correct 43 ms 113044 KB Output is correct
21 Incorrect 44 ms 113040 KB Output isn't correct
22 Halted 0 ms 0 KB -