Submission #118250

#	Time	Username	Problem	Language	Result	Execution time	Memory
118250		onjo0127	Bitaro, who Leaps through Time (JOI19_timeleap)	C++11	100 / 100	1027 ms	82912 KiB

timeleap

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1LL * 1e18;

struct Node { long long ll, lr, rl, rr; };

Node comb(Node X, Node Y) {
	Node ret;
	ret.ll = max(X.ll + Y.rl, X.lr + Y.ll);
	ret.lr = max({X.ll + Y.rr, X.lr + Y.lr, 0LL});
	ret.rl = max({X.rl + Y.rl, X.rr + Y.ll, 0LL});
	ret.rr = max(X.rl + Y.rr, X.rr + Y.lr);
	return ret;
}

struct segtree {
	vector<Node> T;
	segtree(int sz) {
		T.resize(4*sz);
	}
	Node get(int idx, int s, int e, int l, int r) {
		if(r < s || e < l) return {-INF, 0, 0, -INF};
		if(l <= s && e <= r) return T[idx];
		int m = s+e >> 1;
		return comb(get(idx*2, s, m, l, r), get(idx*2+1, m+1, e, l, r));
	}
	void upd(int idx, int s, int e, int p, int S, int E) {
		if(p < s || e < p) return;
		if(s == e) {
			T[idx].ll = S;
			T[idx].rr = -E;
			T[idx].lr = T[idx].rl = 0;
			return;
		}
		int m = s+e >> 1;
		upd(idx*2, s, m, p, S, E);
		upd(idx*2+1, m+1, e, p, S, E);
		T[idx] = comb(T[idx*2], T[idx*2+1]);
	}
};

int L[300009], R[300009];

int main() {
	int N, Q; scanf("%d%d",&N,&Q);
	for(int i=1; i<N; i++) scanf("%d%d",&L[i],&R[i]);
	segtree AC(N), CA(N);
	for(int i=1; i<N; i++) AC.upd(1, 1, N-1, i, L[i] - i, R[i] - 1 - i);
	for(int i=1; i<N; i++) CA.upd(1, 1, N-1, i, L[N-i] - i, R[N-i] - 1 - i);

	while(Q--) {
		int ty; scanf("%d",&ty);
		if(ty == 1) {
			int P, S, E; scanf("%d%d%d",&P,&S,&E);
			AC.upd(1, 1, N-1, P, S - P, E - 1 - P);
			P = N - P;
			CA.upd(1, 1, N-1, P, S - P, E - 1 - P);
		}
		if(ty == 2) {
			int A, B, C, D; scanf("%d%d%d%d",&A,&B,&C,&D);
			if(A < C) {
				B -= A; D -= C;
				Node st = {B, 0, -INF, -B}, en = {D, 0, -INF, -D};
				printf("%lld\n", comb(comb(st, AC.get(1, 1, N-1, A, C-1)), en).lr);
			}
			if(C < A) {
				A = N - A + 1; C = N - C + 1;
				B -= A; D -= C;
				Node st = {B, 0, -INF, -B}, en = {D, 0, -INF, -D};
				printf("%lld\n", comb(comb(st, CA.get(1, 1, N-1, A, C-1)), en).lr);
			}
			if(A == C) printf("%lld\n", 1LL * max(B - D, 0));
		}
	}
	return 0;
}

Compilation message (stderr)

timeleap.cpp: In member function 'Node segtree::get(int, int, int, int, int)':
timeleap.cpp:25:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
timeleap.cpp: In member function 'void segtree::upd(int, int, int, int, int, int)':
timeleap.cpp:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = s+e >> 1;
           ~^~
timeleap.cpp: In function 'int main()':
timeleap.cpp:46:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, Q; scanf("%d%d",&N,&Q);
            ~~~~~^~~~~~~~~~~~~~
timeleap.cpp:47:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<N; i++) scanf("%d%d",&L[i],&R[i]);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~
timeleap.cpp:53:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int ty; scanf("%d",&ty);
           ~~~~~^~~~~~~~~~
timeleap.cpp:55:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int P, S, E; scanf("%d%d%d",&P,&S,&E);
                 ~~~~~^~~~~~~~~~~~~~~~~~~
timeleap.cpp:61:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int A, B, C, D; scanf("%d%d%d%d",&A,&B,&C,&D);
                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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