Submission #520541

#	Time	Username	Problem	Language	Result	Execution time	Memory
520541		fatemetmhr	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	0 / 100	613 ms	137132 KiB

timeleap

//  ~Be name khoda~  //

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second
#define cl       clear
#define endll    '\n'

const int maxn  =  1e6   + 10;
const int maxn5 =  3e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  2e18;

struct javab{

	ll ans, st, ft, ub, ch;
	bool rad;
	javab(){
		rad = true;
	}

} node1[maxnt], node2[maxnt];

javab operator +(javab a, javab b){
	if(a.rad)
		return b;
	if(b.rad)
		return a;
	//cout << "operator having " << '\n';
	//cout << a.st << ' ' << a.ft << ' ' << a.ub << ' ' << a.ch << '\n';
	//cout << b.st << ' ' << b.ft << ' ' << b.ub << ' ' << b.ch << '\n';
	javab ret;
	ret.rad = false;
	ret.st = a.st;
	ret.ans = a.ans + b.ans;
	if(a.ft <= b.st){
		ret.ft = b.ft;
		if(a.ch <= a.ub){
			ll ft = a.ft + (a.ub - a.ch + 1);
			if(ft < b.st){
				ret.ub = a.ub;
				ret.ch = ret.ub + 2;
				if(ret.ch == ret.st)
					ret.ch++;
				return ret;
			}
			ret.ub = a.ub;
			if(ft > b.ub)
				ret.ub -= ft - b.ub;
			
			ft = a.ft + (a.ch <= ret.ub ? ret.ub - a.ch + 1 : 0);
			if(ft >= b.ch)
				ret.ch = ret.ub - (ft - b.ch);
			else
				ret.ch = ret.ub + 2;
			if(ret.ch == ret.st)
				ret.ch++;
			return ret;
		}
		ret.ub = a.ub;
		ret.ch = a.ch;
		if(ret.ch == ret.st)
			ret.ch++;
		return ret;
	}
	
	if(a.ft > b.ub){
		ret.ans += a.ft - b.ub;
		ret.ft = b.ft + (b.ch <= b.ub ? b.ub - b.ch + 1 : 0);
		ret.ub = a.ch - 1;
		ret.ch = ret.ub + 2;
		return ret;
	}
	
	ret.ft = b.ft + (a.ft >= b.ch ? a.ft - b.ch + 1 : 0);
	ll ft = a.ft + (a.ub >= a.ch ? a.ub - a.ch + 1 : 0);
	if(ft > b.ub){
		a.ub -= ft - b.ub;
		ft = b.ub;
	}
	//cout << a.ub << '\n';
	ret.ub = min(a.ub, a.ch + b.ub - a.ft - 1);
	if(ret.ub < a.ch){
		ret.ch = ret.ub + 2;
	}
	else{
		ret.ch = a.ch;
		if(b.ch > a.ft + 1){
			if(b.ch > ft){
				ret.ch = ret.ub + 2;
			}
			else{
				ret.ch += b.ch - (a.ft + 1);
			}
		}
	}
	
	if(ret.ch == a.st)
		ret.ch++;
	return ret;
}

ll ls[maxn5], rs[maxn5];

inline javab recal(javab a, ll ti){
	javab b;
	b.rad = false;
	b.st = ti;
	b.ft = ti;
	b.ub = ti;
	b.ch = ti + 2;
	b.ans = 0;
	return b + a;
}

inline void build(int l, int r, int v){
	if(r - l == 1){
		node1[v].ans = node2[v].ans = 0;
		node1[v].st = node2[v].st = ls[l];
		node1[v].ft = node2[v].ft = ls[l] + 1;
		node1[v].ub = node2[v].ub = rs[l] - 1;
		node1[v].ch = node2[v].ch = ls[l] + 1;
		node1[v].rad = node2[v].rad = false;
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, v * 2);
	build(mid, r, v * 2 + 1);
	node1[v] = node1[v * 2] + node1[v * 2 + 1];
	node2[v] = node2[v * 2 + 1] + node2[v * 2];
	return;
}

inline void upd(int l, int r, int ind, int v){
	if(r - l == 1){
		node1[v].ans = node2[v].ans = 0;
		node1[v].st = node2[v].st = ls[l];
		node1[v].ft = node2[v].ft = ls[l] + 1;
		node1[v].ub = node2[v].ub = rs[l] - 1;
		node1[v].ch = node2[v].ch = ls[l] + 1;
		node1[v].rad = node2[v].rad = false;
		return;
	}
	int mid = (l + r) >> 1;
	if(ind < mid)
		upd(l, mid, ind, v * 2);
	else
		upd(mid, r, ind, v * 2 + 1);
	node1[v] = node1[v * 2] + node1[v * 2 + 1];
	node2[v] = node2[v * 2 + 1] + node2[v * 2];
	return;
}

inline javab get1(int l, int r, int lq, int rq, int v){
	if(rq <= l || r <= lq){
		javab a;
		return a;
	}
	if(lq <= l && r <= rq){
		//cout << "perfect result of " << l << ' ' << r << '\n';
		//cout << node1[v].st << ' ' << node1[v].ft << ' ' << node1[v].ub << ' ' << node1[v].ch << '\n';
		return node1[v];
	}
	//cout << "very well " << l << ' ' << r << '\n';
	int mid = (l + r) >> 1;
	return get1(l, mid, lq, rq, v * 2) + get1(mid, r, lq, rq, v * 2 + 1);
}	

inline javab get2(int l, int r, int lq, int rq, int v){
	if(rq <= l || r <= lq){
		javab a;
		return a;
	}
	if(lq <= l && r <= rq){
		//cout << "perfect result of " << l << ' ' << r << '\n';
		//cout << node2[v].st << ' ' << node2[v].ft << ' ' << node2[v].ub << ' ' << node2[v].ch << '\n';
		return node2[v];
	}
	//cout << "very well " << l << ' ' << r << '\n';
	int mid = (l + r) >> 1;
	return get2(mid, r, lq, rq, v * 2 + 1) + get2(l, mid, lq, rq, v * 2);
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	int n, q; cin >> n >> q;
	n--;
	for(int i = 0; i < n; i++)
		cin >> ls[i] >> rs[i];
	
	build(0, n, 1);
	for(int i = 0; i < q; i++){
		int ty; cin >> ty;
		if(ty == 1){
			int p, s, e; cin >> p >> s >> e;
			p--;
			ls[p] = s;
			rs[p] = e;
			upd(0, n, p, 1);
		}
		else{
			ll a, b, c, d; cin >> a >> b >> c >> d;
			a--; c--;
			if(a == c){
				cout << (b > d ? b - d : 0) << '\n';
				continue;
			}
			javab re;
			if(a < c){
				re = get1(0, n, a, c, 1);
			}
			else{
				re = get2(0, n, c, a, 1);
			}
			
			//cout << re.st << ' ' << re.ft << ' ' << re.ans << ' ' << re.ub << ' ' << re.ch << '\n';
			
			re = recal(re, b);
			if(re.ft > d)
				re.ans += re.ft - d;
			cout << re.ans << '\n';
		}
	}
}

/*
5 1
3 5
4 8
2 6
5 10
2 5 3 1 10


3 1
0 5
0 5
2 1 3 3 3
*/

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