Submission #578499

#	Time	Username	Problem	Language	Result	Execution time	Memory
578499		alireza_kaviani	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	2710 ms	128512 KiB

timeleap

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

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

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())
#define lc          id << 1
#define rc          lc | 1

const ll MAXN = 3e5 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

ll n , q , L[2][MAXN] , R[2][MAXN] , mn[2][MAXN << 2] , mx[2][MAXN << 2];
pair<pll , pll> seg[2][MAXN << 2];
pll ans;

int Find(int ind , int x , int id , int l , int r){
	if(mx[ind][id] <= x && x <= mn[ind][id])	return -1;
	if(r - l == 1)	return (x < mx[ind][id]);
	int mid = l + r >> 1;
	int res = Find(ind , x , lc , l , mid);
	if(res != -1)	return res;
	return Find(ind , x , rc , mid , r);
}

pll mergeOne(pll x , int ind , int id , int l , int r){
	int res = Find(ind , x.Y , id , l , r);
	if(res == -1)	return x;
	if(res == 0){
		return {x.X + x.Y + seg[ind][id].Y.X - R[ind][l] , seg[ind][id].Y.Y};
	}
	return {x.X + seg[ind][id].X.X , seg[ind][id].X.Y};
}

pair<pll , pll> merge(pair<pll , pll> x , int ind , int id , int l , int r){
	return {mergeOne(x.X , ind , id , l , r) , mergeOne(x.Y , ind , id , l , r)};
}

void build(int ind , int id = 1 , int l = 1 , int r = n){
	if(r - l == 1){
		mn[ind][id] = R[ind][l];
		mx[ind][id] = L[ind][l];
		seg[ind][id] = {{0, L[ind][l]}, {0, R[ind][l]}};
		return;
	}
	int mid = l + r >> 1;
	build(ind , lc , l , mid);
	build(ind , rc , mid , r);
	mn[ind][id] = min(mn[ind][lc] , mn[ind][rc]);
	mx[ind][id] = max(mx[ind][lc] , mx[ind][rc]);
	seg[ind][id] = merge(seg[ind][lc] , ind , rc , mid , r);
}

void modify(int ind , int pos , int id = 1 , int l = 1 , int r = n){
	if(r - l == 1){
		mn[ind][id] = R[ind][l];
		mx[ind][id] = L[ind][l];
		seg[ind][id] = {{0, L[ind][l]}, {0, R[ind][l]}};
		return;
	}
	int mid = l + r >> 1;
	if(pos < mid)	modify(ind , pos , lc , l , mid);
	else	modify(ind , pos , rc , mid , r);
	mn[ind][id] = min(mn[ind][lc] , mn[ind][rc]);
	mx[ind][id] = max(mx[ind][lc] , mx[ind][rc]);
	seg[ind][id] = merge(seg[ind][lc] , ind , rc , mid , r);
}

void get(int ind , int ql , int qr , int id = 1 , int l = 1 , int r = n){
	if(qr <= l || r <= ql)	return;
	if(ql <= l && r <= qr){
		ans = mergeOne(ans , ind , id , l , r);
		return;
	}
	int mid = l + r >> 1;
	get(ind , ql , qr , lc , l , mid);
	get(ind , ql , qr , rc , mid , r);
}

void update(int ind , int i , int l , int r){
	L[ind][i] = l - (i - 1);
	R[ind][i] = r - (i - 1);
	modify(ind , i);
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n >> q;
	for(int i = 1 ; i < n ; i++){
		cin >> L[0][i] >> R[0][i];
		R[0][i]--;
		L[1][n - i] = L[0][i];
		R[1][n - i] = R[0][i];
	}
	for(int i = 1 ; i < n ; i++){
		L[0][i] -= i - 1; R[0][i] -= i - 1;
		L[1][i] -= i - 1; R[1][i] -= i - 1;
	}
	if(n != 1){
		build(0);
		build(1);
	}
	while(q--){
		int type , pos , l , r , x , y;
		cin >> type;
		if(type == 1){
			cin >> pos >> l >> r; r--;
			if(n == 1)	continue;
			update(0 , pos , l , r);
			update(1 , n - pos , l , r);
		}
		else{
			cin >> l >> x >> r >> y;
			if(n == 1){
				cout << max(0 , x - y) << endl;
				continue;
			}
			if(l <= r){
				x -= (l - 1); y -= (r - 1);
				ans = {0 , x};
				get(0 , l , r);
//				cout << ans.X << sep << ans.Y << sep << x << sep << y << endl;
				cout << ans.X + max(0ll , ans.Y - y) << endl;
			}
			else{
				l = n + 1 - l; r = n + 1 - r;
				x -= (l - 1); y -= (r - 1);
				ans = {0 , x};
				get(1 , l , r);
//				cout << ans.X << sep << ans.Y << sep << x << sep << y << endl;
				cout << ans.X + max(0ll , ans.Y - y) << endl;
			}
		}
	}

    return 0;
}
/*

*/

Compilation message (stderr)

timeleap.cpp: In function 'int Find(int, int, int, int, int)':
timeleap.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |  int mid = l + r >> 1;
      |            ~~^~~
timeleap.cpp: In function 'void build(int, int, int, int)':
timeleap.cpp:55:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |  int mid = l + r >> 1;
      |            ~~^~~
timeleap.cpp: In function 'void modify(int, int, int, int, int)':
timeleap.cpp:70:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |  int mid = l + r >> 1;
      |            ~~^~~
timeleap.cpp: In function 'void get(int, int, int, int, int, int)':
timeleap.cpp:84:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |  int mid = l + r >> 1;
      |            ~~^~~

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