Submission #118229

#	Time	Username	Problem	Language	Result	Execution time	Memory
118229		sebinkim	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	0 / 100	592 ms	103428 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;
			
			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;
		}
	}
	
	void print()
	{
		if(t == 1) printf("type 1 : %lld %lld\n", l, r);
		else printf("type 2 : %lld %lld -> %lld -> (%lld) -> %lld\n", l, r, x1, v, x2);
	}
};

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

bool test(ll x, node n1, node n2)
{
	node n3 = n1 + n2;
	ll x1, v1, x2, v2, _v;
	tie(x1, v1) = n3.pass(x);
	tie(x2, _v) = n1.pass(x);
	tie(x2, v2) = n2.pass(x2);
	v2 += _v;
	
	if(x1 != x2) return 1;
	if(v1 != v2) return 1;
	return 0;
}

void update(node *T, ll p)
{
	p = p + sz >> 1;
	for(; p; p>>=1){
		if(test(T[p << 1].l, T[p << 1], T[p << 1 | 1])) 1 / 0;
		if(test(T[p << 1].r, T[p << 1], T[p << 1 | 1])) 1 / 0;
		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;
}
/*
node get_sum(node *T, ll l, ll r)
{
	node ret = T[sz + l];
	ll i;
	for(i=l+1; i<=r; i++){
		ret = ret + T[sz + i];
	}
	return ret;
}
*/

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=1; i<n-2; i++){
		printf("%lld %lld %lld\n", i, i + 1, i + 2);
		(T1[sz + i] + (T1[sz + i + 1] + T1[sz + i + 2])).print();
		((T1[sz + i] + T1[sz + i + 1]) + T1[sz + i + 2]).print();
	}
*/	
	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:106:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  p = p + sz >> 1;
      ~~^~~~
timeleap.cpp:108:53: warning: division by zero [-Wdiv-by-zero]
   if(test(T[p << 1].l, T[p << 1], T[p << 1 | 1])) 1 / 0;
                                                   ~~^~~
timeleap.cpp:108:53: warning: statement has no effect [-Wunused-value]
timeleap.cpp:109:53: warning: division by zero [-Wdiv-by-zero]
   if(test(T[p << 1].r, T[p << 1], T[p << 1 | 1])) 1 / 0;
                                                   ~~^~~
timeleap.cpp:109:53: warning: statement has no effect [-Wunused-value]
timeleap.cpp: In function 'node get_sum(node*, ll, ll)':
timeleap.cpp:130:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   l = l + 1 >> 1;
       ~~^~~
timeleap.cpp:131:9: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   r = r - 1 >> 1;
       ~~^~~
timeleap.cpp: In function 'int main()':
timeleap.cpp:159: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:169: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:186:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &t);
   ~~~~~^~~~~~~~~~~~
timeleap.cpp:188: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:194: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: 0 / 4
• Subtask 2: 0 / 30
• Subtask 3: 0 / 66