Submission #126762

#	Time	Username	Problem	Language	Result	Execution time	Memory
126762		TadijaSebez	Bitaro, who Leaps through Time (JOI19_timeleap)	C++11	100 / 100	1420 ms	67780 KiB

timeleap

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=300050;
const int M=4*N;
const ll inf=1e18;
struct Node
{
	ll l,r,cost,go;
	Node():l(-inf),r(inf),cost(0),go(inf){}
	Node(ll _l, ll _r, ll _cost, ll _go):l(_l),r(_r),cost(_cost),go(_go){}
};
Node operator + (Node a, Node b)
{
	Node ans;
	if(a.go!=inf) ans=Node(a.l,a.r,a.cost+max(a.go-b.r,(ll)0),max(min(a.go,b.r),b.l));
	else if(a.r<b.l) ans=Node(a.r,a.r,0,b.l);
	else if(a.l>b.r) ans=Node(a.l,a.l,a.l-b.r,b.r);
	else if(b.go!=inf) return b;
	else ans=Node(max(a.l,b.l),min(a.r,b.r),0,inf);
	if(b.go!=inf) ans.go=b.go,ans.cost+=b.cost;
	return ans;
}
int ls[M],rs[M],root[2],tsz,n;
Node node[M];
void Set(int &c, int ss, int se, int qi, int l, int r)
{
	if(!c) c=++tsz;
	if(ss==se){ node[c]=Node(l-qi,r-qi-1,0,inf);return;}
	int mid=ss+se>>1;
	if(qi<=mid) Set(ls[c],ss,mid,qi,l,r);
	else Set(rs[c],mid+1,se,qi,l,r);
	node[c]=node[ls[c]]+node[rs[c]];
}
Node Get(int c, int ss, int se, int qs, int qe)
{
	if(qs>qe || qs>se || ss>qe) return Node();
	if(qs<=ss && qe>=se) return node[c];
	int mid=ss+se>>1;
	return Get(ls[c],ss,mid,qs,qe)+Get(rs[c],mid+1,se,qs,qe);
}
void Upd(int x, int l, int r)
{
	Set(root[0],1,n-1,x,l,r);
	Set(root[1],1,n-1,n-x,l,r);
}
int main()
{
	int q,t,x,y,l,r;
	scanf("%i %i",&n,&q);
	for(int i=1;i<n;i++) scanf("%i %i",&l,&r),Upd(i,l,r);
	while(q--)
	{
		scanf("%i",&t);
		if(t==1) scanf("%i %i %i",&x,&l,&r),Upd(x,l,r);
		else
		{
			scanf("%i %i %i %i",&x,&l,&y,&r);
			if(x==y) printf("%i\n",max(l-r,0));
			else
			{
				int rt=0;
				if(x>y) rt=1,x=n-x+1,y=n-y+1;
				Node ans=Node(l-x,l-x,0,inf)+Get(root[rt],1,n-1,x,y-1)+Node(r-y,r-y,0,inf);
				printf("%lld\n",ans.cost);
			}
		}
	}
	return 0;
}

Compilation message (stderr)

timeleap.cpp: In function 'void Set(int&, int, int, int, int, int)':
timeleap.cpp:30:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
timeleap.cpp: In function 'Node Get(int, int, int, int, int)':
timeleap.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
timeleap.cpp: In function 'int main()':
timeleap.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
timeleap.cpp:51:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<n;i++) scanf("%i %i",&l,&r),Upd(i,l,r);
                       ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
timeleap.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i",&t);
   ~~~~~^~~~~~~~~
timeleap.cpp:55:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if(t==1) scanf("%i %i %i",&x,&l,&r),Upd(x,l,r);
            ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
timeleap.cpp:58:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%i %i %i %i",&x,&l,&y,&r);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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