Submission #132692

#	Time	Username	Problem	Language	Result	Execution time	Memory
132692		hamzqq9	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	0 / 100	814 ms	87928 KiB

timeleap

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define ll long long
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define inf 20000000
#define N 300005
#define MOD 998244353
#define KOK 700		
using namespace std;

struct range {

	int lb,rb;
	int ps;
	ll cost;
	int near;

};

struct seg {

	range pre,suf;

} S[N*4];

int n,q;
int l[N],r[N];

range combine(range l,range r) {

	range res;

	tie(res.lb,res.rb)=tie(l.lb,l.rb); // lb,rb

	int ct=l.ps;

	//cerr<<"ct : "<<ct<<"\n";

	res.cost=l.cost+r.cost; // cost ~~~~

	if(ct<=r.lb) {

		res.lb=r.lb-1;
	
		umax(res.rb,r.lb-1);

		l.near=res.rb-res.lb;
	
		res.near=min(l.near,r.near); // near
		res.ps=r.ps; // ps

	}
	else {

		int df=ct-r.lb;

		if(df>r.near) {

			int dfn=df-r.near;

			res.cost+=dfn; // cost +
			if(r.near) res.ps=r.ps+r.near; // ps
			else res.ps=r.ps;
			r.near=0; // near

		}
		else {

			res.ps=r.ps+df;
			r.near-=df;

		}

		res.near=min(l.near,r.near);

	}

	return res;

}

seg merge(seg a,seg b) {

	seg res;

	res.pre=combine(a.pre,b.pre);
	res.suf=combine(b.suf,a.suf);

	return res;

}

seg get_naive(int id) {

	seg res;

	res.suf=res.pre={l[id],r[id],l[id]+1,0,r[id]-l[id]};

	return res;

}

seg get(int node,int bas,int son,int l,int r) {

	if(bas>=l && son<=r) return S[node];

	if(orta>l && orta<r) return merge(get(node<<1,bas,orta,l,r),get(node<<1|1,orta,son,l,r));
	if(orta>l) return get(node<<1,bas,orta,l,r);

	return get(node<<1|1,orta,son,l,r);

}

void up(int node,int bas,int son,int l,int r) {

	if(bas==l && son==r) {

		S[node]=get_naive(bas);

		return ;

	}

	if(bas>=r || son<=l) return ;

	up(node<<1,bas,orta,l,r);
	up(node<<1|1,orta,son,l,r);

	S[node]=merge(S[node<<1],S[node<<1|1]);

}

void build(int node,int bas,int son) {

	if(bas+1==son) {

		S[node]=get_naive(bas);

		return ;

	}

	build(node<<1,bas,orta);
	build(node<<1|1,orta,son);

	S[node]=merge(S[node<<1],S[node<<1|1]);

}

int main() {

	scanf("%d %d",&n,&q);

	for(int i=1;i<n;i++) {

		scanf("%d %d",l+i,r+i);

		r[i]--;

	}

	build(1,1,n);

	//cerr<<get(1,1,n,1,5).suf.ps<<"\n";

	//return 0;	

	while(q--) {

		int t;

		scanf("%d",&t);

		if(t==1) {

			int a,b,c;

			scanf("%d %d %d",&a,&b,&c);

			tie(l[a],r[a])={b,c};

			r[a]--;

			up(1,1,n,a,a+1);

		}
		else {

			int a,b,c,d;

			scanf("%d %d %d %d",&a,&b,&c,&d);

			range f={b,b,b,0,inf};
			range s={d,d,d,0,0};
			range ans;

			if(a!=c) {

				seg res=get(1,1,n,min(a,c),max(a,c));

				ans=(a<c?res.pre:res.suf);
	
				//cerr<<ans.cost<<' '<<ans.ps<<"\n";

				ans=combine(f,ans);

				ans=combine(ans,s);

			}
			else {

				ans=combine(f,s);

			}

			printf("%lld\n",ans.cost);

		}

	}
  
}

Compilation message (stderr)

timeleap.cpp: In function 'int main()':
timeleap.cpp:160:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
timeleap.cpp:164:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",l+i,r+i);
   ~~~~~^~~~~~~~~~~~~~~~~
timeleap.cpp:180:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&t);
   ~~~~~^~~~~~~~~
timeleap.cpp:186:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d",&a,&b,&c);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:199:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d %d",&a,&b,&c,&d);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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