Submission #105253

#	Time	Username	Problem	Language	Result	Execution time	Memory
105253		Just_Solve_The_Problem	Bitaro, who Leaps through Time (JOI19_timeleap)	C++11	100 / 100	1186 ms	68832 KiB

timeleap

#include <bits/stdc++.h>

#define fr first
#define sc second
#define ll long long

using namespace std;

const int N = (int)3e5 + 7;

int n, q;
pair<int, int> ar[N];

struct node {
	ll l, r, cost, to;
	node() {
		l = -1e18;
		r = 1e18;
		cost = -1;
		to = 0;
	}
	node(ll _l, ll _r, ll _cost, ll _to) {
		l = _l;
		r = _r;
		cost = _cost;
		to = _to;
	}
};

node merge(node a, node b) {
	if (a.cost != -1) {
		a.cost += max(a.to - b.r, 0LL);
		a.to = max(b.l, min(a.to, b.r));
		if (b.cost != -1) {
			a.to = b.to;
			a.cost += b.cost;
		}
	} else if (a.l > b.r) {
		a = {a.l, a.l, a.l - b.r, b.r};
		if (b.cost != -1) {
			a.to = b.to;
			a.cost += b.cost;
		}
	} else if (a.r < b.l) {
		a = {a.r, a.r, 0, b.l};
		if (b.cost != -1) {
			a.to = b.to;
			a.cost += b.cost;
		}
	} else if (b.cost != -1) {
		a = b;
	} else {
		a.l = max(a.l, b.l);
		a.r = min(a.r, b.r);
	}
	return a;
}
node tree[N * 4];

void upd(int pos, node val, int v = 1, int l = 1, int r = n) {
	if (l == r) {
		tree[v] = val;
		return ;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) {
		upd(pos, val, v + v, l, mid);
	} else {
		upd(pos, val, v + v + 1, mid + 1, r);
	}
	tree[v] = merge(tree[v + v], tree[v + v + 1]);
}

node get(int l, int r, int v = 1, int tl = 1, int tr = n) {
	if (tl > r || tr < l) return node();
	if (l <= tl && tr <= r) return tree[v];
	int mid = (tl + tr) >> 1;
	return merge(get(l, r, v + v, tl, mid), get(l, r, v + v + 1, mid + 1, tr));
}

int A[N], B[N], C[N], D[N], tp[N];
ll ans[N];

main() {
	scanf("%d %d", &n, &q);
	for (int i = 1; i < n; i++) {
		scanf("%d %d", &ar[i].fr, &ar[i].sc);
		upd(i, node(ar[i].fr - i, ar[i].sc - i - 1, -1, 0));
	}
	for (int i = 1; i <= q; i++) {
		scanf("%d", &tp[i]);
		if (tp[i] == 1) {
			scanf("%d %d %d", &A[i], &B[i], &C[i]);
			upd(A[i], node(B[i] - A[i], C[i] - A[i] - 1, -1, 0));
 		} else {
			scanf("%d %d %d %d", &A[i], &B[i], &C[i], &D[i]);
			if (A[i] > C[i]) continue;
			B[i] -= A[i];
			D[i] -= C[i];
			if (A[i] == C[i]) {
				ans[i] = max(B[i] - D[i], 0);
				B[i] += A[i];
				D[i] += C[i];
				continue;
			}
			//node asd = get(A[i], C[i] - 1);
			//cout << asd.l << ' ' << asd.r << ' ' << asd.cost << ' ' << asd.to << '\n';
			ans[i] = merge(node(B[i], B[i], 0, B[i]), merge(get(A[i], C[i] - 1), node(D[i], D[i], 0, D[i]))).cost;
			B[i] += A[i];
			D[i] += C[i];
 		}
	}
	for (int i = 1; i < n; i++) {
		upd(n - i, node(ar[i].fr + i + 1, ar[i].sc + i, -1, 0));
	}
	for (int i = 1; i <= q; i++) {
		if (tp[i] == 1) {
			upd(n - A[i], node(B[i] + A[i] + 1, C[i] + A[i], -1, 0));
		} else {
			if (A[i] <= C[i]) continue;
			B[i] += A[i];
			D[i] += C[i];
			//node asd = get(n - A[i] + 1, n - C[i]);
			//cout << asd.l << ' ' << asd.r << ' ' << asd.cost << ' ' << asd.to << '\n';
			ans[i] = merge(node(B[i], B[i], 0, B[i]), merge(get(n - A[i] + 1, n - C[i]), node(D[i], D[i], 0, D[i]))).cost;
		}
	}
	for (int i = 1; i <= q; i++) {
		if (tp[i] == 2) {
			printf("%lld\n", ans[i]);
		}
	}
}

Compilation message (stderr)

timeleap.cpp:84:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
timeleap.cpp: In function 'int main()':
timeleap.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
timeleap.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &ar[i].fr, &ar[i].sc);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &tp[i]);
   ~~~~~^~~~~~~~~~~~~~
timeleap.cpp:93:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &A[i], &B[i], &C[i]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:96:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d %d", &A[i], &B[i], &C[i], &D[i]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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