Submission #516915

#	Time	Username	Problem	Language	Result	Execution time	Memory
516915		Koosha_mv	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	0 / 100	999 ms	524292 KiB

timeleap

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll

const int N=13e5+99,S=2,inf=2e9;

int n,q,a[N],b[N],c[N],d[N],T[N],Ans[N];
vector<int> Q[N];
int seg[N][S][S];

void make(int x){
	if(x==0){
		f(i,0,n){
			a[i]=c[i]-i;
			b[i]=d[i]-i;
		}
	}
	else{
		f(i,0,n){
			a[i]=c[n-i-1]-i;
			b[i]=d[n-i-1]-i;
		}
		f(i,0,q){
			if(T[i]==1){
				Q[i][0]=n-Q[i][0]-1;
			}
			else{
				Q[i][0]=n-Q[i][0];
				Q[i][2]=n-Q[i][2];
			}
		}
	}
}
void reset(){
	f(i,0,S) f(j,0,S) seg[0][i][j]=(i==j ? -inf : 0);
}
void merge(int id,int u,int v){
	int res[S][S];
	f(i,0,S) f(j,0,S) res[i][j]=(i==j ? -inf : 0);
	f(i,0,2){
		f(j,0,2){
			f(p,0,2){
				int k=j^1;
				maxm(res[i][p],seg[u][i][j]+seg[v][k][p]);
			}
		}
	}
	f(i,0,S) f(j,0,S) seg[id][i][j]=res[i][j];
}
void add(int u,int v){
	int id=N-5;
	f(i,0,S) f(j,0,S) seg[id][i][j]=(i==j ? -inf : 0);
	seg[id][0][0]=u;
	merge(0,id,0);
	f(i,0,S) f(j,0,S) seg[id][i][j]=(i==j ? -inf : 0);
	seg[id][1][1]=-v;
	merge(0,0,id);
}
void build(int id=1,int l=0,int r=n){
	if(l+1==r){
		seg[id][0][0]=a[l];
		seg[id][1][1]=-b[l];
		seg[id][0][1]=0;
		seg[id][1][0]=0;
		return ;
	}
	int mid=(l+r)>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid,r);
	merge(id,id<<1,id<<1|1);
}
void change(int id,int l,int r,int x){
	if(r<=x || x<l) return ;
	if(l+1==r){
		seg[id][0][0]=a[l];
		seg[id][1][1]=-b[l];
		seg[id][0][1]=0;
		seg[id][1][0]=0;
		return ;
	}
	int mid=(l+r)>>1;
	change(id<<1,l,mid,x);
	change(id<<1|1,mid,r,x);
	merge(id,id<<1,id<<1|1);
}
void get(int id,int l,int r,int L,int R){
	if(R<=L) return ;
	if(r<=L || R<=l) return ;
	if(L<=l && r<=R){
		merge(0,0,id);
		return ;
	}	
	int mid=(l+r)>>1;
	get(id<<1,l,mid,L,R);
	get(id<<1|1,mid,r,L,R);
}
void solve(){
	build();
	f(i,0,q){
		int t,x,l,r;
		if(T[i]==1){
			x=Q[i][0],l=Q[i][1],r=Q[i][2];
			a[x]=l-x;
			b[x]=r-x;
			change(1,0,n,x);
		}
		else{
			int s,e,t,p,ans=0;
			s=Q[i][0],e=Q[i][1],t=Q[i][2],p=Q[i][3];
			
			if(s<=t){
				int b1=e-s,b2=p-t;
				if(s==t){
					maxm(Ans[i],b1-b2);
				}
				else{
					reset();
					get(1,0,n,s,t);
					add(b1,b2);
					maxm(Ans[i],seg[0][0][1]);
				}
			}
		}
	}
}

main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n>>q; n--;
	f(i,0,n){
		cin>>c[i]>>d[i];
		d[i]--;
	}	
	f(i,0,q){
		cin>>T[i];
		if(T[i]==1){
			int x,l,r;
			cin>>x>>l>>r;
			x--; r--;
			Q[i].pb(x);
			Q[i].pb(l);
			Q[i].pb(r);
		}
		else{
			int s,e,t,p;
			cin>>s>>e>>t>>p;
			s--,t--;
			Q[i].pb(s);
			Q[i].pb(e);
			Q[i].pb(t);
			Q[i].pb(p);
		}
	}
	make(0);
	solve();
	make(1);
	solve();
	f(i,0,q){
		if(T[i]==2){
			cout<<Ans[i]<<endl;
		}
	}
}
/*
3 1
0 5
0 5
2 1 3 3 3
1 2 0 1
2 1 3 3 3

*/

Compilation message (stderr)

timeleap.cpp: In function 'void solve()':
timeleap.cpp:126:16: warning: unused variable 'ans' [-Wunused-variable]
  126 |    int s,e,t,p,ans=0;
      |                ^~~
timeleap.cpp:118:7: warning: unused variable 't' [-Wunused-variable]
  118 |   int t,x,l,r;
      |       ^
timeleap.cpp: At global scope:
timeleap.cpp:145:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  145 | main(){
      | ^~~~

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