oj.uz

Submission #118192

# Submission time Handle Problem Language Result Execution time Memory
118192 2019-06-18T10:34:48 Z sebinkim Bitaro, who Leaps through Time (JOI19_timeleap) C++14
4 / 100
 3000 ms 99152 KB 
#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;

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;
}
*/
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=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

timeleap.cpp: In function 'void update(node*, ll)':
timeleap.cpp:92:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  p = p + sz >> 1;
      ~~^~~~
timeleap.cpp: In function 'int main()':
timeleap.cpp:142: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:152: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:163:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &t);
   ~~~~~^~~~~~~~~~~~
timeleap.cpp:165: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:171: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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 640 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 4 ms 768 KB Output is correct
14 Correct 4 ms 640 KB Output is correct
15 Correct 4 ms 640 KB Output is correct
16 Correct 4 ms 640 KB Output is correct
17 Correct 4 ms 512 KB Output is correct
18 Correct 4 ms 512 KB Output is correct
19 Correct 4 ms 640 KB Output is correct
20 Correct 4 ms 640 KB Output is correct
21 Correct 3 ms 640 KB Output is correct
22 Correct 5 ms 548 KB Output is correct
23 Correct 7 ms 640 KB Output is correct
24 Correct 4 ms 640 KB Output is correct
25 Correct 4 ms 640 KB Output is correct
26 Correct 4 ms 512 KB Output is correct
27 Correct 4 ms 640 KB Output is correct
28 Correct 4 ms 640 KB Output is correct
29 Correct 4 ms 640 KB Output is correct
30 Correct 4 ms 640 KB Output is correct
31 Correct 4 ms 640 KB Output is correct
32 Correct 3 ms 512 KB Output is correct
33 Correct 4 ms 512 KB Output is correct
34 Correct 3 ms 512 KB Output is correct
35 Correct 3 ms 632 KB Output is correct
36 Correct 4 ms 640 KB Output is correct
37 Correct 4 ms 640 KB Output is correct
38 Correct 4 ms 640 KB Output is correct
39 Correct 3 ms 512 KB Output is correct
40 Correct 4 ms 640 KB Output is correct
41 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3046 ms 99152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 640 KB Output is correct
12 Correct 4 ms 640 KB Output is correct
13 Correct 4 ms 768 KB Output is correct
14 Correct 4 ms 640 KB Output is correct
15 Correct 4 ms 640 KB Output is correct
16 Correct 4 ms 640 KB Output is correct
17 Correct 4 ms 512 KB Output is correct
18 Correct 4 ms 512 KB Output is correct
19 Correct 4 ms 640 KB Output is correct
20 Correct 4 ms 640 KB Output is correct
21 Correct 3 ms 640 KB Output is correct
22 Correct 5 ms 548 KB Output is correct
23 Correct 7 ms 640 KB Output is correct
24 Correct 4 ms 640 KB Output is correct
25 Correct 4 ms 640 KB Output is correct
26 Correct 4 ms 512 KB Output is correct
27 Correct 4 ms 640 KB Output is correct
28 Correct 4 ms 640 KB Output is correct
29 Correct 4 ms 640 KB Output is correct
30 Correct 4 ms 640 KB Output is correct
31 Correct 4 ms 640 KB Output is correct
32 Correct 3 ms 512 KB Output is correct
33 Correct 4 ms 512 KB Output is correct
34 Correct 3 ms 512 KB Output is correct
35 Correct 3 ms 632 KB Output is correct
36 Correct 4 ms 640 KB Output is correct
37 Correct 4 ms 640 KB Output is correct
38 Correct 4 ms 640 KB Output is correct
39 Correct 3 ms 512 KB Output is correct
40 Correct 4 ms 640 KB Output is correct
41 Correct 2 ms 384 KB Output is correct
42 Execution timed out 3046 ms 99152 KB Time limit exceeded
43 Halted 0 ms 0 KB -