Submission #691715

#	Time	Username	Problem	Language	Result	Execution time	Memory
691715		flappybird	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	656 ms	96348 KiB

timeleap

#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(0) { }
	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 (stderr)

timeleap.cpp: In function 'node operator+(node, node)':
timeleap.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
   61 | }
      | ^

• Subtask 1: 4 / 4
• Subtask 2: 30 / 30
• Subtask 3: 66 / 66