Submission #201588

#	Time	Username	Problem	Language	Result	Execution time	Memory
201588		red1108	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	0 / 100	723 ms	136948 KiB

timeleap

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define eb emplace_back
#define em emplace
#define prec(a) cout<<fixed;cout.precision(a);
#define all(a) (a).begin(), (a).end()
typedef long long ll;typedef long double ld;typedef unsigned long long ul;typedef unsigned int ui;typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const ll INF = 2e18;
const int inf = 2e9;
template<class T>
void pr(T t) {cerr << t << " ";}
template<class T, class ...Args>
void pr(T a, Args ...args) {cerr << a << " ";pr(args...);}
template<class ...Args>
void prl(Args ...args) {pr(args...);cerr << endl;}

int n,q,in[300010][2];
struct Node{
	ll b,x,ls,le,rs,re,si=0;
	Node(){};
	Node(ll bb,int xx,int i,int j,int k,int l){b=bb;x=xx;ls=i;le=j;rs=k;re=l;}
	Node operator +(Node B){
		B.x--;B.ls--;B.le--;
		Node p = Node(b,x,ls,le,rs,re);
		if(p.re>B.x) p.x-=(p.re-B.x);
		if(p.x<p.ls){
			p.b+=(p.ls-p.x);
			p.x=p.ls;
		}
		p.b+=B.b;
		ll t = B.re-B.rs, ss = B.rs-B.si-1;
		p.rs = max(p.rs,B.ls);
		p.re = max(p.re,B.ls);
		if(p.rs<=ss) p.rs = B.rs;
		else p.rs = B.rs + min(p.rs-ss,t);
		if(p.re<=ss) p.re = B.rs;
		else p.re = B.rs + min(p.re-ss,t);
		p.si = si + B.si + 1;
		return p;
	}
	void pr(){
		prl("b=",b,"x=",x,"[",ls,",",le,"]","   [",rs,",",re,"]");
	}
};
vector<Node> help;
struct SEG{
	Node val[1200000];
	void init(int x, int l, int r, bool t){
		if(l==r){
			if(t)val[x]=Node(0,in[l][1],in[l][0],in[l][1],in[l][0],in[l][1]);
			else val[x]=Node(0,in[n-l][1],in[n-l][0],in[n-l][1],in[n-l][0],in[n-l][1]);
			return ;
		}
		init(x*2,l,(l+r)/2,t);
		init(x*2+1,(l+r)/2+1,r,t);
		val[x]=val[x*2]+val[x*2+1];
	}
	void gang(int x, int l, int r, int ind, bool t){
		if(r<ind||ind<l) return ;
		if(l==r){
			if(t)val[x]=Node(0,in[l][1],in[l][0],in[l][1],in[l][0],in[l][1]);
			else val[x]=Node(0,in[n-l][1],in[n-l][0],in[n-l][1],in[n-l][0],in[n-l][1]);
			return ;
		}
		gang(x*2,l,(l+r)/2,ind,t);
		gang(x*2+1,(l+r)/2+1,r,ind,t);
		val[x]=val[x*2]+val[x*2+1];
	}
	void query(int x, int l, int r,int s, int e){
		if(r<s||e<l) return ;
		if(s<=l&&r<=e){
			help.eb(val[x]);return ;
		}
		query(x*2,l,(l+r)/2,s,e);
		query(x*2+1,(l+r)/2+1,r,s,e);
	}
	void debug(int x, int l, int r){
		prl("#######x=",x,"l=",l,"r=",r);
		val[x].pr();
		if(l==r)return ;
		debug(x*2,l,(l+r)/2);debug(x*2+1,(l+r)/2+1,r);
	}
}seg1, seg2;
ll eval(ll s, ll e){
	for(int i=0;i<help.size()-1;i++) help[i]=help[i]+help[i+1];
	s = max(help[0].ls,s);
	ll ret = help[0].b + max(s-help[0].x,0LL);
	ll ss = help[0].rs-help[0].si;
	ll t = help[0].rs+1;
	if(s>ss) t = help[0].rs + min(help[0].re-help[0].rs,s-ss)+1;
	ret+=max(t-e,0LL);
	return ret;
}
int main(){
	fastio;
	cin>>n>>q;
	for(int i=1;i<n;i++){
		cin>>in[i][0]>>in[i][1];
		in[i][1]--;
	}
	seg1.init(1,1,n-1,1);
	seg2.init(1,1,n-1,0);
	//prl("seg1");seg1.debug(1,1,n-1);
	//prl("seg2");seg2.debug(1,1,n-1);
	while(q--){
		int a,b,c,d;
		cin>>a;
		if(a==1){
			cin>>a>>b>>c;
			in[a][0]=b;in[a][1]=c-1;
			seg1.gang(1,1,n-1,a,1);
			seg2.gang(1,1,n-1,n-a,0);
			/*
			prl("after query=================");
	prl("seg1");seg1.debug(1,1,n-1);
	prl("seg2");seg2.debug(1,1,n-1);
	*/
		}
		else{
			cin>>a>>b>>c>>d;
			help.clear();
			ll ans=0;
			if(a<c){
				seg1.query(1,1,n-1,a,c-1);
				ans = eval(b,d);
			}
			else if(a>c){
				a = n-a;c = n-c;
				seg2.query(1,1,n-1,a+1,c);
				ans = eval(b,d);
			}
			else ans = max(b-d,0);
			cout<<ans<<"\n";
		}
	}
}

Compilation message (stderr)

timeleap.cpp: In function 'll eval(ll, ll)':
timeleap.cpp:92:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<help.size()-1;i++) help[i]=help[i]+help[i+1];
              ~^~~~~~~~~~~~~~

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