Submission #103028

#	Time	Username	Problem	Language	Result	Execution time	Memory
103028		jangwonyoung	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	100 / 100	1233 ms	71672 KiB

timeleap

#include<iostream>
using namespace std;
typedef long long ll;
int n,q;
ll l[300001],r[300001];
int t[300001],p[300001];
ll s[300001],e[300001];
int a[300001],c[300001];
ll b[300001],d[300001];
ll ans[300001];
struct info{
	ll l,r;
	ll cost,to;
};
info zero={(ll)-1e18,(ll)1e18,-1,0};
info f(info l,info r){
	if(l.cost!=-1){
		l.cost+=max(l.to-r.r,0LL);
		l.to=min(r.r,max(l.to,r.l));
		if(r.cost!=-1) l.to=r.to,l.cost+=r.cost;
	}
	else if(l.l>r.r){
		l={l.l,l.l,l.l-r.r,r.r};
		if(r.cost!=-1) l.to=r.to,l.cost+=r.cost;
	}
	else if(l.r<r.l){
		l={l.r,l.r,0,r.l};
		if(r.cost!=-1) l.to=r.to,l.cost+=r.cost;
	}
	else if(r.cost!=-1) l=r;
	else{
		l={max(l.l,r.l),min(l.r,r.r),-1,168};
	}
	return l;
}
info g[1<<20];
void upd(int id,int l,int r,int up,ll us,ll ue){
	if(l==r){
		g[id]={us,ue,-1,168};
		return;
	}
	int mid=(l+r)/2;
	if(up<=mid) upd(id*2,l,mid,up,us,ue);
	else upd(id*2+1,mid+1,r,up,us,ue);
	g[id]=f(g[id*2],g[id*2+1]);
}
info qry(int id,int l,int r,int ql,int qr){
	if(l>qr || r<ql) return zero;
	if(ql<=l && r<=qr) return g[id];
	int mid=(l+r)/2;
	return f(qry(id*2,l,mid,ql,qr),qry(id*2+1,mid+1,r,ql,qr));
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> q;
	for(int i=1; i<n ;i++) cin >> l[i] >> r[i];
	for(int i=1; i<n ;i++) upd(1,1,n,i,l[i]-i,r[i]-i-1);
	for(int i=1; i<=q ;i++){
		cin >> t[i];
		if(t[i]==1){
			cin >> p[i] >> s[i] >> e[i];
			upd(1,1,n,p[i],s[i]-p[i],e[i]-p[i]-1);
		}
		else{
			cin >> a[i] >> b[i] >> c[i] >> d[i];
			if(a[i]>c[i]) continue;
			if(a[i]==c[i]){
				ans[i]=max(b[i]-d[i],0LL);
				continue;
			}
			b[i]-=a[i],d[i]-=c[i];
			info x={b[i],b[i],0,b[i]};
			info y={d[i],d[i],0,d[i]};
			info z=f(x,f(qry(1,1,n,a[i],c[i]-1),y));
			ans[i]=z.cost;
		}
	}
	for(int i=1; i<n ;i++) upd(1,1,n,n-i,l[i]+i+1,r[i]+i);
	for(int i=1; i<=q ;i++){
		if(t[i]==1) upd(1,1,n,n-p[i],s[i]+p[i]+1,e[i]+p[i]);
		else{
			if(a[i]<=c[i]) continue;
			b[i]+=a[i],d[i]+=c[i];
			info x={b[i],b[i],0,b[i]};
			info y={d[i],d[i],0,d[i]};
			info z=f(x,f(qry(1,1,n,n-a[i]+1,n-c[i]),y));
			ans[i]=z.cost;
		}
	}
	for(int i=1; i<=q ;i++) if(t[i]==2) cout << ans[i] << '\n';
}

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