oj.uz

Submission #118400

# Submission time Handle Problem Language Result Execution time Memory
118400 2019-06-18T23:50:27 Z imyujin Bitaro, who Leaps through Time (JOI19_timeleap) C++14
4 / 100
 264 ms 25696 KB 
#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[3*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]=0;
		seg[idx].t[1]=LL[l];
		seg[idx].t[2]=-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]=0;
		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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Correct 4 ms 512 KB Output is correct
15 Correct 4 ms 640 KB Output is correct
16 Correct 5 ms 640 KB Output is correct
17 Correct 4 ms 640 KB Output is correct
18 Correct 4 ms 640 KB Output is correct
19 Correct 4 ms 512 KB Output is correct
20 Correct 4 ms 640 KB Output is correct
21 Correct 4 ms 512 KB Output is correct
22 Correct 4 ms 512 KB Output is correct
23 Correct 4 ms 512 KB Output is correct
24 Correct 4 ms 640 KB Output is correct
25 Correct 4 ms 512 KB Output is correct
26 Correct 4 ms 512 KB Output is correct
27 Correct 4 ms 512 KB Output is correct
28 Correct 4 ms 640 KB Output is correct
29 Correct 4 ms 512 KB Output is correct
30 Correct 4 ms 512 KB Output is correct
31 Correct 4 ms 512 KB Output is correct
32 Correct 4 ms 512 KB Output is correct
33 Correct 4 ms 512 KB Output is correct
34 Correct 4 ms 512 KB Output is correct
35 Correct 5 ms 512 KB Output is correct
36 Correct 4 ms 512 KB Output is correct
37 Correct 4 ms 640 KB Output is correct
38 Correct 4 ms 512 KB Output is correct
39 Correct 4 ms 512 KB Output is correct
40 Correct 6 ms 512 KB Output is correct
41 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 264 ms 25696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 5 ms 512 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Correct 4 ms 512 KB Output is correct
15 Correct 4 ms 640 KB Output is correct
16 Correct 5 ms 640 KB Output is correct
17 Correct 4 ms 640 KB Output is correct
18 Correct 4 ms 640 KB Output is correct
19 Correct 4 ms 512 KB Output is correct
20 Correct 4 ms 640 KB Output is correct
21 Correct 4 ms 512 KB Output is correct
22 Correct 4 ms 512 KB Output is correct
23 Correct 4 ms 512 KB Output is correct
24 Correct 4 ms 640 KB Output is correct
25 Correct 4 ms 512 KB Output is correct
26 Correct 4 ms 512 KB Output is correct
27 Correct 4 ms 512 KB Output is correct
28 Correct 4 ms 640 KB Output is correct
29 Correct 4 ms 512 KB Output is correct
30 Correct 4 ms 512 KB Output is correct
31 Correct 4 ms 512 KB Output is correct
32 Correct 4 ms 512 KB Output is correct
33 Correct 4 ms 512 KB Output is correct
34 Correct 4 ms 512 KB Output is correct
35 Correct 5 ms 512 KB Output is correct
36 Correct 4 ms 512 KB Output is correct
37 Correct 4 ms 640 KB Output is correct
38 Correct 4 ms 512 KB Output is correct
39 Correct 4 ms 512 KB Output is correct
40 Correct 6 ms 512 KB Output is correct
41 Correct 2 ms 384 KB Output is correct
42 Runtime error 264 ms 25696 KB Execution killed with signal 11 (could be triggered by violating memory limits)
43 Halted 0 ms 0 KB -