Submission #102082

#	Time	Username	Problem	Language	Result	Execution time	Memory
102082		ainta	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	1851 ms	98564 KiB

timeleap

#include<cstdio>
#include<algorithm>
#include<vector>
#define SZ 1048576
#define N_ 601000
using namespace std;
const int INF = 2e9;
struct AA {
	struct Tree {
		long long M, L, R, LR;
	}IT[SZ + SZ];
	Tree Merge(Tree a, Tree b) {
		long long L = max(max(a.M + b.L, a.L + b.LR),a.L);
		long long R = max(max(b.M + a.R, b.R + a.LR),b.R);
		long long LR = max(max(a.LR,b.LR),max(a.R + b.L, a.LR + b.LR));
		long long M = max(a.M + b.M, a.L + b.R);
		Tree ret = { M,L,R,LR };
		return ret;
	}
	void Make(int a, long long l, long long r) {
		//printf("%d %lld %lld\n", a, l, r);
		a += SZ;
		IT[a] = { 0, l, -r, l - r };
		while (a != 1) {
			a >>= 1;
			IT[a] = Merge(IT[a * 2], IT[a * 2 + 1]);
		}
	};
	long long Get(int b, int e) {
		b += SZ, e += SZ;
		vector<int>T1, T2;
		while (b <= e) {
			if (b & 1) {
				T1.push_back(b);
			}
			if (!(e & 1)) {
				T2.push_back(e);
			}
			b = (b + 1) >> 1, e = (e - 1) >> 1;
		}
		reverse(T2.begin(), T2.end());
		for (auto &t : T2)T1.push_back(t);
		if (T1.empty())return 0;
		Tree ret = IT[T1[0]];
		for (int i = 1; i < T1.size(); i++)ret = Merge(ret, IT[T1[i]]);
		return ret.M;
	}
	long long Solve(int b, int e, int bT, int eT) {
		Make(b * 2, bT - b, INF);
		Make(e * 2, -INF, eT - e);
		long long res = Get(b * 2, e * 2);
		Make(b * 2, -INF, INF);
		Make(e * 2, -INF, INF);
		return res;
	}
}Right, Left;
int n, Q, LL[N_], RR[N_];
int main() {
	//freopen("input.txt", "r", stdin);
	int i, ck, a, b, c, d;
	scanf("%d%d", &n, &Q);
	for (i = 1; i < n; i++) {
		scanf("%d%d", &LL[i], &RR[i]);
		Left.Make(i * 2 + 1, LL[i] - i, RR[i] - i - 1);
		Right.Make((n - i) * 2 + 1, LL[i] - (n-i), RR[i] - (n-i) - 1);
	}
	for (i = 1; i <= n; i++) {
		Left.Make(i * 2, -INF, INF);
		Right.Make(i * 2, -INF, INF);
	}
	while (Q--) {
		scanf("%d", &ck);
		if (ck == 1) {
			scanf("%d%d%d", &a, &b, &c);
			Left.Make(a * 2 + 1, b - a, c - a - 1);
			Right.Make((n - a) * 2 + 1, b - (n-a), c - (n-a) - 1);
		}
		else {
			scanf("%d%d%d%d", &a, &b, &c, &d);
			if (a == c) {
				printf("%d\n", max(b - d, 0));
			}
			else if (a < c) {
				printf("%lld\n", Left.Solve(a, c, b, d));
			}
			else {
				printf("%lld\n", Right.Solve(n + 1 - a, n + 1 - c, b, d));
			}
		}
	}
	return 0;
}

Compilation message (stderr)

timeleap.cpp: In member function 'long long int AA::Get(int, int)':
timeleap.cpp:45:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < T1.size(); i++)ret = Merge(ret, IT[T1[i]]);
                   ~~^~~~~~~~~~~
timeleap.cpp: In function 'int main()':
timeleap.cpp:61: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:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &LL[i], &RR[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &ck);
   ~~~~~^~~~~~~~~~~
timeleap.cpp:74:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%d", &a, &b, &c);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:79:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d%d%d", &a, &b, &c, &d);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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