Submission #210356

#	Time	Username	Problem	Language	Result	Execution time	Memory
210356		DrumpfTheGodEmperor	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	4 / 100	3051 ms	15096 KiB

timeleap

#include <bits/stdc++.h>
#define int long long
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define out(s) freopen(s, "w", stdout);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
		freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 3e5 + 5;
int n, q, l[N], r[N], l2[N], r2[N];
signed main() {
	#ifdef BLU
	in("blu.inp");
	#endif
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	fw (i, 0, n - 1) {
		cin >> l[i] >> r[i];
		l2[n - 2 - i] = l[i], r2[n - 2 - i] = r[i];
	}
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int road, s, e;
			cin >> road >> s >> e;
			road--;
			l[road] = s, r[road] = e;
			l2[n - 2 - road] = s, r2[n - 2 - road] = e;
		} else {
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			a--, c--;
			if (a == c) {
				if (b < d) cout << "0\n";
				else cout << b - d << "\n";
			} else if (a < c) {
				int ans = 0, cur = b - a;
				fw (i, a, c + 1) {
					int lval = l[i], rval = r[i];
					if (i == c) rval = d + 1;
					
					ans += max(0ll, cur + i - rval + 1);
					
					cur = min(cur, rval - i - 1);
					cur = max(cur, lval - i);
				}
				cout << ans << "\n";
			} else {
				a = n - 1 - a, c = n - 1 - c;
				assert(a < c);
				
				int ans = 0, cur = b - a;
				fw (i, a, c + 1) {
					int lval = l2[i], rval = r2[i];
					if (i == c) rval = d + 1;
					
					ans += max(0ll, cur + i - rval + 1);
					
					cur = min(cur, rval - i - 1);
					cur = max(cur, lval - i);
				}
				cout << ans << "\n";
			}
		}
	}
	return 0;
}

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