Submission #118402

#	Time	Username	Problem	Language	Result	Execution time	Memory
118402		imyujin	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	100 / 100	2439 ms	87544 KiB

timeleap

#include<stdio.h>
#include<algorithm>

using namespace std;

#define MAXN 300005

struct st{
	long long t[4];
};

const long long LINF=1ll<<60;
int N, Q;
int L[MAXN], R[MAXN];
int T[MAXN], A[MAXN], B[MAXN], C[MAXN], D[MAXN];
int LL[2*MAXN], RR[2*MAXN];
st seg[8*MAXN];
int a[4][4]={{0, 0, 1, 2}, {0, 1, 1, 3}, {2, 0, 3, 2}, {2, 1, 3, 3}};

void updseg(int x, int idx, int l, int r){
	if(l==r){
		seg[idx].t[0]=seg[idx].t[3]=0ll;
		seg[idx].t[1]=(long long)LL[l];
		seg[idx].t[2]=-(long long)RR[l];
		return;
	}
	int m=(l+r)/2;
	if(x<=m) updseg(x, idx*2, l, m);
	else updseg(x, idx*2+1, m+1, r);
	for(int i=0; i<4; i++)
		seg[idx].t[i]=max(seg[idx*2].t[a[i][0]]+seg[idx*2+1].t[a[i][1]], seg[idx*2].t[a[i][2]]+seg[idx*2+1].t[a[i][3]]);
}

st gseg(int s, int e, int idx, int l, int r){
	st ans;
	if(s<=l&&r<=e) return seg[idx];
	if(e<l||r<s){
		ans.t[0]=ans.t[3]=0ll;
		ans.t[1]=ans.t[2]=-LINF;
		return ans;
	}
	int m=(l+r)/2;
	st r1=gseg(s, e, idx*2, l, m), r2=gseg(s, e, idx*2+1, m+1, r);
	for(int i=0; i<4; i++)
		ans.t[i]=max(r1.t[a[i][0]]+r2.t[a[i][1]], r1.t[a[i][2]]+r2.t[a[i][3]]);
	return ans;
}

void update(int x){
	LL[x]=L[x]-x;
	RR[x]=R[x]-x;
	updseg(x, 1, 0, 2*N+1);
	LL[2*N+1-x]=L[x]+x;
	RR[2*N+1-x]=R[x]+x;
	updseg(2*N+1-x, 1, 0, 2*N+1);
}

int main(){
	//freopen("input.txt", "r", stdin);

	scanf("%d%d", &N, &Q);
	for(int i=1; i<N; i++) scanf("%d%d", L+i, R+i);
	for(int i=0; i<Q; i++){
		scanf("%d%d%d%d", T+i, A+i, B+i, C+i);
		if(T[i]==2) scanf("%d", D+i);
	}

	for(int i=1; i<N; i++){
		R[i]--;
		update(i);
	}
	//for(int i=0; i<=2*N+1; i++) printf("%d %d\n", LL[i], RR[i]);
	//printf("\n");
	
	for(int i=0; i<Q; i++){
		if(T[i]==1){
			L[A[i]]=B[i];
			R[A[i]]=C[i]-1;
			update(A[i]);
		}
		else{
			if(A[i]<C[i]){
				int la=L[A[i]-1], ra=R[A[i]-1], lc=L[C[i]], rc=R[C[i]];
				L[A[i]-1]=R[A[i]-1]=B[i]-1;
				update(A[i]-1);
				L[C[i]]=R[C[i]]=D[i];
				update(C[i]);
				//for(int i=0; i<2*N+2; i++) printf("%d %d\n", LL[i], RR[i]);
				printf("%lld\n", gseg(A[i]-1, C[i], 1, 0, 2*N+1).t[0]);
				L[A[i]-1]=la;
				R[A[i]-1]=ra;
				update(A[i]-1);
				L[C[i]]=lc;
				R[C[i]]=rc;
				update(C[i]);
			}
			else{
				int la=L[A[i]], ra=R[A[i]], lc=L[C[i]-1], rc=R[C[i]-1];
				L[A[i]]=R[A[i]]=B[i]-1;
				update(A[i]);
				L[C[i]-1]=R[C[i]-1]=D[i];
				update(C[i]-1);
				//for(int i=0; i<2*N+2; i++) printf("%d %d\n", LL[i], RR[i]);
				printf("%lld\n", gseg(2*N+1-A[i], 2*N-C[i]+2, 1, 0, 2*N+1).t[0]);
				L[A[i]]=la;
				R[A[i]]=ra;
				update(A[i]);
				L[C[i]-1]=lc;
				R[C[i]-1]=rc;
				update(C[i]-1);
			}
			///printf("****\n");
			//for(int i=0; i<2*N+2; i++) printf("%d %d\n", LL[i], RR[i]);
			//printf("\n");
		}
	}

	return 0;
}

Compilation message (stderr)

timeleap.cpp: In function 'int main()':
timeleap.cpp:61: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:62:30: 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("%d%d", L+i, R+i);
                         ~~~~~^~~~~~~~~~~~~~~~~~
timeleap.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", T+i, A+i, B+i, C+i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:65:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if(T[i]==2) scanf("%d", D+i);
               ~~~~~^~~~~~~~~~~

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