Submission #1006412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006412		AdamGS	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	100 / 100	380 ms	71508 KiB

timeleap

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
struct item {
	ll t=0, a=0, b=0, c=0;
};
const ll INF=1e18+7;
const int LIM=3e5+7;
item tr[2][4*LIM];
int N=1;
item merge(item a, item b) {
	item x;
	x.c=a.c+b.c;
	if(a.t==0 && b.t==0) {
		x.a=max(a.a, b.a);
		x.b=min(a.b, b.b);
		if(x.a<=x.b) return x;
		if(a.a>b.b) {
			x.a=a.a;
			x.b=b.b;
			x.c+=a.a-b.b;
		} else {
			x.a=a.b;
			x.b=b.a;
		}
		x.t=1;
		return x;
	}
	x.t=1;
	if(b.t==0) {
		x.a=a.a;
		if(a.b>=b.b) {
			x.b=b.b;
			x.c+=a.b-b.b;
		} else if(a.b<=b.a) x.b=b.a;
		else x.b=a.b;
		return x;
	}
	x.b=b.b;
	if(a.t==0) {
		if(a.a>=b.a) {
			x.c+=a.a-b.a;
			x.a=a.a;
		} else if(a.b<=b.a) x.a=a.b;
		else x.a=b.a;
	} else {
		x.a=a.a;
		if(a.b>=b.a) x.c+=a.b-b.a;
	}
	return x;
}
void upd(int v, int k, item p) {
	v+=N;
	tr[k][v]=p;
	v/=2;
	while(v) {
		tr[k][v]=merge(tr[k][2*v], tr[k][2*v+1]);
		v/=2;
	}
}
item cnt(int l, int r, int k) {
	if(l>r) return {0, -INF, INF, 0};
	l+=N; r+=N;
	item ansl=tr[k][l];
	if(l==r) return ansl;
	item ansr=tr[k][r];
	while(l/2!=r/2) {
		if(l%2==0) ansl=merge(ansl, tr[k][l+1]);
		if(r%2==1) ansr=merge(tr[k][r-1], ansr);
		l/=2; r/=2;
	}
	return merge(ansl, ansr);
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q;
	cin >> n >> q;
	while(N<n) N*=2;
	rep(i, n-1) {
		ll a, b;
		cin >> a >> b; --b;
		tr[0][N+i]={0, a-i, b-i, 0};
		tr[1][N+n-i-2]={0, a-(n-i-2), b-(n-i-2), 0};
	}
	for(int i=N-1; i; --i) {
		tr[0][i]=merge(tr[0][2*i], tr[0][2*i+1]);
		tr[1][i]=merge(tr[1][2*i], tr[1][2*i+1]);
	}
	while(q--) {
		int t;
		cin >> t;
		if(t==2) {
			ll a, b, c, d;
			cin >> a >> b >> c >> d; --a; --c;
			if(a<=c) {
				b-=a; d-=c;
				item x={1, b, b, 0}, y={1, d, d, 0};
				x=merge(x, cnt(a, c-1, 0));
				x=merge(x, y);
				cout << x.c << '\n';
				continue;
			}
			b-=(n-a-1); d-=(n-c-1);
			item x={1, b, b, 0}, y={1, d, d, 0};
			item xd=cnt(n-a-1, n-c-2, 1);
			x=merge(x, cnt(n-a-1, n-c-2, 1));
			x=merge(x, y);
			cout << x.c << '\n';
		} else {
			ll a, b, c;
			cin >> a >> b >> c; --a; --c;
			upd(a, 0, {0, b-a, c-a, 0});
			upd(n-a-2, 1, {0, b-(n-a-2), c-(n-a-2), 0});
		}
	}
}

Compilation message (stderr)

timeleap.cpp: In function 'int main()':
timeleap.cpp:111:9: warning: variable 'xd' set but not used [-Wunused-but-set-variable]
  111 |    item xd=cnt(n-a-1, n-c-2, 1);
      |         ^~

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