oj.uz

Submission #691714

# Submission time Handle Problem Language Result Execution time Memory
691714 2023-01-31T13:05:42 Z flappybird Bitaro, who Leaps through Time (JOI19_timeleap) C++17
0 / 100
 572 ms 93856 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 301010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
struct node {
	ll down, up, fin, cst;
	node() {
		down = -INF;
		up = INF;
		fin = -1;
		cst = 0;
	}
	node(ll down, ll up) :down(down), up(up), fin(down == up ? down : -1), cst(cst) { }
	node(ll down, ll up, ll fin, ll cst) :down(down), up(up), fin(fin), cst(cst) { }
};
inline node operator+(node n1, node n2) {
	int c1, c2;
	c1 = n1.down == n1.up;
	c2 = n2.down == n2.up;
	if (!c1 && !c2) {
		if (n1.down >= n2.up) return node(n1.down, n1.down, n2.up, n1.down - n2.up);
		if (n1.up <= n2.down) return node(n1.up, n1.up, n2.down, n2.down - n1.up);
		return node(max(n1.down, n2.down), min(n1.up, n2.up), -1, 0);
	}
	if (c1 && !c2) {
		node ret;
		ret.cst = n1.cst;
		ret.up = ret.down = n1.up;
		if (n1.fin > n2.up) ret.fin = n2.up, ret.cst += n1.fin - n2.up;
		else if (n1.fin < n2.down) ret.fin = n2.down, ret.cst += n2.down - n1.fin;
		else ret.fin = n1.fin;
		return ret;
	}
	if (!c1 && c2) {
		node ret;
		ret.fin = n2.fin;
		ret.cst = n2.cst;
		if (n1.down > n2.up) ret.up = ret.down = n1.down, ret.cst += n1.down - n2.up;
		else if (n1.up < n2.up) ret.up = ret.down = n1.up, ret.cst += n2.up - n1.up;
		else ret.up = ret.down = n2.up;
		return ret;
	}
	if (c1 && c2) {
		node ret;
		ret.up = ret.down = n1.up;
		ret.fin = n2.fin;
		ret.cst = n1.cst + n2.cst + abs(n1.fin - n2.up);
		return ret;
	}
}
inline ll get(node n, ll sy, ll ey) {
	ll fe;
	ll ans = 0;
	if (n.up == n.down) fe = n.fin, ans += n.cst + abs(n.up - sy);
	else {
		if (n.down <= sy && sy <= n.up) fe = sy;
		else if (n.down > sy) fe = n.down, ans += n.down - sy;
		else fe = n.up, ans += sy - n.up;
	}
	return ans + abs(ey - fe);
}
node narr[MAX];
namespace segtree {
	node tree[MAX * 4];
	void init(int s, int e, int loc = 1) {
		if (s == e) {
			tree[loc] = narr[s];
			return;
		}
		int m = (s + e) >> 1;
		init(s, m, loc * 2);
		init(m + 1, e, loc * 2 + 1);
		tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
	}
	void upd(int s, int e, int x, node n, int loc = 1) {
		if (e < x || x < s) return;
		if (s == e) {
			tree[loc] = n;
			return;
		}
		int m = (s + e) >> 1;
		upd(s, m, x, n, loc * 2);
		upd(m + 1, e, x, n, loc * 2 + 1);
		tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
	}
	node query(int s, int e, int l, int r, int loc = 1) {
		if (l <= s && e <= r) return tree[loc];
		if (e < l || r < s) return node();
		int m = (s + e) >> 1;
		return query(s, m, l, r, loc * 2) + query(m + 1, e, l, r, loc * 2 + 1);
	}
}
int N, M;
ll P[MAX];
ll S[MAX];
ll E[MAX];
vector<int> qv[MAX];
ll A[MAX];
ll B[MAX];
ll C[MAX];
ll D[MAX];
ll qt[MAX];
ll L[MAX];
ll R[MAX];
ll ans[MAX];
void solve() {
	int i;
	for (i = 1; i <= N; i++) narr[i] = node(L[i] - i, R[i] - i - 1);
	segtree::init(1, N - 1);
	for (i = 0; i <= M + 1; i++) {
		if (1 <= i && i <= M) segtree::upd(1, N - 1, P[i], node(S[i] - P[i], E[i] - P[i] - 1));
		for (auto v : qv[i]) {
			ans[v] = get(segtree::query(1, N - 1, A[v], C[v] - 1), B[v] - A[v], D[v] - C[v]);
			ans[v] = (ans[v] - (D[v] - C[v] - B[v] + A[v])) / 2;
		}
	}
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int Q;
	cin >> N >> Q;
	int i;
	for (i = 1; i < N; i++) cin >> L[i] >> R[i];
	int op;
	for (i = 1; i <= Q; i++) {
		cin >> op;
		if (op == 1) {
			M++;
			cin >> P[M] >> S[M] >> E[M];
		}
		else {
			cin >> A[i] >> B[i] >> C[i] >> D[i], qt[i] = M;
			if (A[i] == C[i]) ans[i] = max(0ll, B[i] - D[i]);
		}
	}
	if (N == 1) {
		for (i = 1; i <= Q; i++) if (A[i]) cout << ans[i] << Ln;
		return 0;
	}
	for (i = 1; i <= Q; i++) if (A[i] && A[i] < C[i]) qv[qt[i]].push_back(i);
	solve();
	for (i = 1; i <= N / 2; i++) swap(L[i], L[N - i]), swap(R[i], R[N - i]);
	for (i = 1; i <= M; i++) P[i] = N - P[i];
	for (i = 1; i <= Q; i++) if (A[i]) A[i] = N + 1 - A[i], C[i] = N + 1 - C[i];
	for (i = 0; i <= M; i++) qv[i].clear();
	for (i = 1; i <= Q; i++) if (A[i] && A[i] < C[i]) qv[qt[i]].push_back(i);
	solve();
	for (i = 1; i <= Q; i++) if (A[i]) cout << ans[i] << ln;
}

Compilation message

timeleap.cpp: In constructor 'node::node(ll, ll)':
timeleap.cpp:24:2: warning: 'node::cst' is initialized with itself [-Winit-self]
   24 |  node(ll down, ll up) :down(down), up(up), fin(down == up ? down : -1), cst(cst) { }
      |  ^~~~
timeleap.cpp: In function 'node operator+(node, node)':
timeleap.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
   61 | }
      | ^
timeleap.cpp: In constructor 'node::node(ll, ll)':
timeleap.cpp:24:77: warning: '*<unknown>.node::cst' is used uninitialized in this function [-Wuninitialized]
   24 |  node(ll down, ll up) :down(down), up(up), fin(down == up ? down : -1), cst(cst) { }
      |                                                                             ^~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 54484 KB Output is correct
2 Correct 27 ms 54476 KB Output is correct
3 Correct 26 ms 54504 KB Output is correct
4 Correct 26 ms 54484 KB Output is correct
5 Correct 25 ms 54500 KB Output is correct
6 Correct 26 ms 54484 KB Output is correct
7 Correct 25 ms 54520 KB Output is correct
8 Correct 27 ms 54464 KB Output is correct
9 Correct 27 ms 54476 KB Output is correct
10 Correct 26 ms 54572 KB Output is correct
11 Correct 27 ms 54628 KB Output is correct
12 Correct 27 ms 54604 KB Output is correct
13 Correct 26 ms 54640 KB Output is correct
14 Correct 27 ms 54644 KB Output is correct
15 Correct 26 ms 54704 KB Output is correct
16 Correct 26 ms 54644 KB Output is correct
17 Correct 26 ms 54612 KB Output is correct
18 Correct 26 ms 54668 KB Output is correct
19 Correct 26 ms 54656 KB Output is correct
20 Correct 26 ms 54592 KB Output is correct
21 Incorrect 27 ms 54628 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 78012 KB Output is correct
2 Correct 505 ms 92740 KB Output is correct
3 Correct 509 ms 92960 KB Output is correct
4 Correct 497 ms 92620 KB Output is correct
5 Correct 572 ms 93400 KB Output is correct
6 Correct 512 ms 93112 KB Output is correct
7 Incorrect 521 ms 93856 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 54484 KB Output is correct
2 Correct 27 ms 54476 KB Output is correct
3 Correct 26 ms 54504 KB Output is correct
4 Correct 26 ms 54484 KB Output is correct
5 Correct 25 ms 54500 KB Output is correct
6 Correct 26 ms 54484 KB Output is correct
7 Correct 25 ms 54520 KB Output is correct
8 Correct 27 ms 54464 KB Output is correct
9 Correct 27 ms 54476 KB Output is correct
10 Correct 26 ms 54572 KB Output is correct
11 Correct 27 ms 54628 KB Output is correct
12 Correct 27 ms 54604 KB Output is correct
13 Correct 26 ms 54640 KB Output is correct
14 Correct 27 ms 54644 KB Output is correct
15 Correct 26 ms 54704 KB Output is correct
16 Correct 26 ms 54644 KB Output is correct
17 Correct 26 ms 54612 KB Output is correct
18 Correct 26 ms 54668 KB Output is correct
19 Correct 26 ms 54656 KB Output is correct
20 Correct 26 ms 54592 KB Output is correct
21 Incorrect 27 ms 54628 KB Output isn't correct
22 Halted 0 ms 0 KB -