Submission #118187

#	Time	Username	Problem	Language	Result	Execution time	Memory
118187		imyujin	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	0 / 100	313 ms	31324 KiB

timeleap

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

using namespace std;

#define MAXN 300005

typedef pair<long long, int> pi;

const int INF=1e9;
int N, rn;
int L[MAXN], R[MAXN];
int T[MAXN], A[MAXN], B[MAXN], C[MAXN], D[MAXN];
int LL[2*MAXN], RR[2*MAXN];
int lmax[6*MAXN], rmin[6*MAXN];
int root[800];
pi dp[4*MAXN];

void updseg(int x, int idx, int l, int r){
	if(l==r){
		lmax[idx]=l;
		rmin[idx]=l;
	}
	else{
		int m=(l+r)/2;
		if(x<=m) updseg(x, idx*2, l, m);
		else updseg(x, idx*2+1, m+1, r);
		lmax[idx]=LL[lmax[idx*2]]>=LL[lmax[idx*2+1]]?lmax[idx*2]:lmax[idx*2+1];
		rmin[idx]=RR[rmin[idx*2]]<=RR[rmin[idx*2+1]]?rmin[idx*2]:rmin[idx*2+1];
	}
}

int gbigl(int x, int y, int idx, int l, int r){
	//printf("*x=%d, y=%d, l=%d, r=%d\n", x, y, l, r);
	if(LL[lmax[idx]]<y) return r+1;
	if(l==r) return l;
	int m=(l+r)/2;
	if(x>m) return gbigl(x, y, idx*2+1, m+1, r);
	int t=gbigl(x, y, idx*2, l, m);
	return t==m+1?gbigl(x, y, idx*2+1, m+1, r):t;
}

int gsmar(int x, int y, int idx, int l, int r){
	if(RR[rmin[idx]]>y) return r+1;
	if(l==r) return l;
	int m=(l+r)/2;
	if(x>m) return gsmar(x, y, idx*2+1, m+1, r);
	int t=gsmar(x, y, idx*2, l, m);
	return t==m+1?gsmar(x, y, idx*2+1, m+1, r):t;
}

pi move(int x1, int x2, int y1){
	int x=x1, y=y1<2*N?LL[y1]:RR[y1-2*N];
	pi ans=make_pair(0, y1);
	while(x<x2){
		x++;
		if(LL[x]>y){
			ans.second=x;
			y=LL[x];
		}
		else if(RR[x]<y){
			ans.first+=y-RR[x];
			ans.second=x+2*N;
			y=RR[x];
		}
	}
	return ans;
}

int gr(int x){
	int r=0;
	while(r<rn&&root[r+1]<=x) r++;
	return r;
}

void update(int x, int l, int r){
	//printf("[%d %d %d]\n", x, l, r);
	LL[x]=l;
	RR[x]=r;
	updseg(x, 1, 0, 2*N-3);
	r=gr(x);
	if(r>0) for(int i=root[r-1]; i<root[r]; i++) for(int j=i; j<=i+2*N; j+=2*N)
		dp[j]=move(root[r], root[r+1], j);
}

void print(){
	for(int i=0; i<2*N-2; i++) printf("%d ", LL[i]);
	printf("\n");
	for(int i=0; i<2*N-2; i++) printf("%d ", RR[i]);
	printf("\n[%d %d]\n", lmax[1], rmin[1]);
	for(int i=0; i<rn-1; i++) for(int j=root[i]; j<root[i+1]; j++) for(int k=j; k<=j+2*N; k+=2*N)
		dp[k]=move(root[i+1], root[i+2], k);
	for(int i=0; i<2; i++) for(int j=0; j<2*N-2; j++) printf("dp[%d]=(%d %d)\n", i*2*N+j, dp[i*2*N+j].first, dp[i*2*N+j].second);
	printf("\n");
}

int main(){
	int Q;

	//freopen("input.txt", "r", stdin);
	scanf("%d%d", &N, &Q);
	for(int i=0; i<N-1; 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=0; i<N-1; i++){
		LL[i]=L[i]-i;
		RR[i]=R[i]-i-1;
		updseg(i, 1, 0, 2*N-3);
		LL[2*N-3-i]=L[i]+i;
		RR[2*N-3-i]=R[i]+i-1;
		updseg(2*N-3-i, 1, 0, 2*N-3);
	}
	for(rn=1; (rn+1)*(rn+1)<=2*N-3; rn++);
	root[0]=0;
	for(int i=1; i<=rn; i++) root[i]=root[i-1]+(2*N-3)/rn+(i<=(2*N-3)%rn?1:0);
	//for(int i=0; i<=rn; i++) printf("%d ", root[i]);
	//printf("\n");
	//print();

	for(int i=0; i<Q; i++){
		if(T[i]==1){
			update(A[i]-1, B[i]-A[i]+1, C[i]-A[i]);
			update(2*N-2-A[i], B[i]+A[i]-1, C[i]+A[i]-2);
			//print();
		}
		else{
			int x1, y1, x2, y2;
			if(A[i]<C[i]){
				x1=A[i]-1;
				y1=B[i]-A[i]+1;
				x2=C[i]-2;
				y2=D[i]-C[i]+1;
			}
			else{
				x1=2*N-1-A[i];
				y1=B[i]+A[i]-2;
				x2=2*N-2-C[i];
				y2=D[i]+C[i]-2;
			}
			//printf("x1=%d, y1=%d, x2=%d, y2=%d\n", x1, y1, x2, y2);
			int lb=gbigl(x1, y1+1, 1, 0, 2*N-3), rs=gsmar(x1, y1-1, 1, 0, 2*N-3);
			//printf("lb=%d, rs=%d\n", lb, rs);
			int k=lb<rs?lb:rs+2*N, x3=min(lb, rs);
			long long ans=lb<rs?0:y1-RR[rs];
			if(x3>x2){
				printf("%d\n", y1<y2?0:y1-y2);
				continue;
			}
			int r1=gr(x3), r2=gr(x2);
			if(r1==r2){
				pi p=move(x3, x2, k);
				int y=p.second<2*N?LL[p.second]:RR[p.second-2*N];
				//printf("x3=%d, x2=%d, k=%d, p=(%d, %d), y=%d\n", x3, x2, k, p.first, p.second, y);
				printf("%lld\n", ans+(y>y2?y-y2:0));
				continue;
			}
			pi p=move(x3, root[r1+1], k);
			//printf("r1=%d, r2=%d, p=(%d, %d)\n", r1, r2, p.first, p.second);
			ans+=p.first;
			for(int j=r1+1; j<r2-1; j++){
				p=move(root[j], root[j+1], p.second);
				ans+=p.first;
			}
			p=move(root[r2], x2, p.second);
			//printf("p=(%d, %d)\n", p.first, p.second);
			ans+=p.first;
			int y=p.second<2*N?LL[p.second]:RR[p.second-2*N];
			printf("%lld\n", ans+(y>y2?y-y2:0));
		}
	}
	return 0;
}

Compilation message (stderr)

timeleap.cpp: In function 'void print()':
timeleap.cpp:93:125: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
  for(int i=0; i<2; i++) for(int j=0; j<2*N-2; j++) printf("dp[%d]=(%d %d)\n", i*2*N+j, dp[i*2*N+j].first, dp[i*2*N+j].second);
                                                                                        ~~~~~~~~~~~~~~~~~                    ^
timeleap.cpp: In function 'int main()':
timeleap.cpp:101: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:102:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N-1; i++) scanf("%d%d", L+i, R+i);
                           ~~~~~^~~~~~~~~~~~~~~~~~
timeleap.cpp:104: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:105: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: 0 / 4
• Subtask 2: 0 / 30
• Subtask 3: 0 / 66