Submission #118238

#	Time	Username	Problem	Language	Result	Execution time	Memory
118238		sebinkim	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	100 / 100	693 ms	119280 KiB

timeleap

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

struct node{
	ll t, l, r, x1, x2, v;
	node() {}
	node(ll l, ll r) : t(1), l(l), r(r) {}
	node(ll l, ll r, ll x) : t(2), l(l), r(r), x1(x), x2(x), v(0) {}
	
	pll pass(ll x)
	{
		if(t == 1){
			if(l <= x && x <= r) return pll(x, 0);
			else if(x < l) return pll(l, 0);
			else return pll(r, x - r);
		}
		else{
			ll _v = v;
			
			if(x < l) x = l;
			else if(r < x) _v += x - r, x = r;
			if(x > x1) _v += x - x1;
			
			return pll(x2, _v);
		}
	}
	
	node operator + (node n)
	{
		if(t == 1 && n.t == 1){
			if(max(l, n.l) <= min(r, n.r)){
				return node(max(l, n.l), min(r, n.r));
			}
			else if(r < n.l) return node(l, r, n.l);
			else return node(l, r, n.r);
		}
		else if(t == 1 && n.t == 2){
			node ret = n;
			ret.l = l; ret.r = r; 
			
			if(max(l, n.l) <= min(r, n.r)){
				ret.l = max(l, n.l);
				ret.r = min(r, n.r);
			}
			else if(r < n.l){
				ret.x1 = n.l;
				if(n.l > n.x1) ret.v += n.l - n.x1;
			}
			else{
				ret.x1 = n.r;
				if(n.r > n.x1) ret.v += n.r - n.x1;
			}
			
			return ret;
		}
		else if(t == 2 && n.t == 1){
			node ret(l, r, x1);
			
			ret.v = v;
			if(n.l <= x2 && x2 <= n.r) ret.x2 = x2;
			else if(x2 < n.l) ret.x2 = n.l;
			else if(n.r < x2) ret.x2 = n.r, ret.v += x2 - n.r;
			
			return ret;
		}
		else{
			node ret(l, r, x1);
			ll _x2, _v;
			
			tie(_x2, _v) = n.pass(x2);
			ret.x2 = _x2; ret.v = v + _v;
			
			return ret;
		}
	}
};

node T1[1101010], T2[1101010];
ll n, sz;

void update(node *T, ll p)
{
	p = p + sz >> 1;
	for(; p; p>>=1){
		T[p] = T[p << 1] + T[p << 1 | 1];
	}
}

node get_sum(node *T, ll l, ll r)
{
	node sl, sr;
	ll fl = 0, fr = 0;
	
	l += sz; r += sz;
	
	for(; l<r; ){
		if(l & 1){
			if(!fl) sl = T[l], fl = 1;
			else sl = sl + T[l];
		}
		if(~r & 1){
			if(!fr) sr = T[r], fr = 1;
			else sr = T[r] + sr;
		}
		l = l + 1 >> 1;
		r = r - 1 >> 1;
	}
	
	if(l == r){
		if(!fl) sl = T[l], fl = 1;
		else sl = sl + T[l];
	}
	
	if(!fl) return sr;
	else if(!fr) return sl;
	else return sl + sr;
}

int main()
{
	ll q, i, t, l, r, x, y, z, s, e, v;
	
	scanf("%lld%lld", &n, &q);
	
	for(sz=1; sz<=n; sz<<=1);
	
	for(i=0; i<sz; i++){
		T1[sz + i] = node(1, 0, 0);
		T2[sz + i] = node(1, 0, 0);
	}
	
	for(i=1; i<n; i++){
		scanf("%lld%lld", &l, &r);
		T1[sz + i] = node(l - i, r - i - 1);
		T2[sz + n - i] = node(l - n + i, r - n + i - 1);
	}
	
	for(i=sz-1; i>=1; i--){
		T1[i] = T1[i << 1] + T1[i << 1 | 1];
		T2[i] = T2[i << 1] + T2[i << 1 | 1];
	}
	
	for(; q--; ){
		scanf("%lld", &t);
		if(t == 1){
			scanf("%lld%lld%lld", &i, &l, &r);
			T1[sz + i] = node(l - i, r - i - 1);
			T2[sz + n - i] = node(l - n + i, r - n + i - 1);
			update(T1, i); update(T2, n - i);
		}
		else{
			scanf("%lld%lld%lld%lld", &s, &x, &e, &y);
			if(s == e) printf("%lld\n", max(0ll, x - y));
			else if(s < e){
				x -= s; y -= e;
				tie(z, v) = get_sum(T1, s, e - 1).pass(x);
				printf("%lld\n", v + max(0ll, z - y));
			}
			else{
				s = n - s + 1; e = n - e + 1;
				x -= s; y -= e;
				tie(z, v) = get_sum(T2, s, e - 1).pass(x);
				printf("%lld\n", v + max(0ll, z - y));
			}
		}
	}
	
	return 0;
}

Compilation message (stderr)

timeleap.cpp: In function 'void update(node*, ll)':
timeleap.cpp:87:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  p = p + sz >> 1;
      ~~^~~~
timeleap.cpp: In function 'node get_sum(node*, ll, ll)':
timeleap.cpp:109:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   l = l + 1 >> 1;
       ~~^~~
timeleap.cpp:110:9: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   r = r - 1 >> 1;
       ~~^~~
timeleap.cpp: In function 'int main()':
timeleap.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
timeleap.cpp:137:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~
timeleap.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &t);
   ~~~~~^~~~~~~~~~~~
timeleap.cpp:150:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld%lld", &i, &l, &r);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:156:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld%lld%lld%lld", &s, &x, &e, &y);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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