oj.uz

Submission #516926

# Submission time Handle Problem Language Result Execution time Memory
516926 2022-01-22T08:25:52 Z Koosha_mv Bitaro, who Leaps through Time (JOI19_timeleap) C++14
0 / 100
 577 ms 96020 KB 
#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--;
			if(n==0) cout<<max(0ll,e+1-p)<<'\n';
			Q[i].pb(s);
			Q[i].pb(e);
			Q[i].pb(t);
			Q[i].pb(p);
		}
	}
	if(n==0) exit(0);
	make(0);
	solve();
	make(1);
	solve();
	f(i,0,q){
		if(T[i]==2){
			cout<<Ans[i]<<'\n';
		}
	}
}
/*
3 1
0 5
0 5
2 1 3 3 3
1 2 0 1
2 1 3 3 3

*/

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 17 ms 30796 KB Output is correct
2 Correct 21 ms 30900 KB Output is correct
3 Correct 17 ms 30808 KB Output is correct
4 Correct 19 ms 30812 KB Output is correct
5 Correct 16 ms 30788 KB Output is correct
6 Correct 16 ms 30796 KB Output is correct
7 Correct 18 ms 30924 KB Output is correct
8 Correct 21 ms 30848 KB Output is correct
9 Correct 17 ms 30868 KB Output is correct
10 Correct 17 ms 30796 KB Output is correct
11 Correct 22 ms 31052 KB Output is correct
12 Correct 20 ms 31036 KB Output is correct
13 Correct 19 ms 31064 KB Output is correct
14 Correct 16 ms 31060 KB Output is correct
15 Correct 24 ms 30960 KB Output is correct
16 Correct 19 ms 31044 KB Output is correct
17 Correct 18 ms 30996 KB Output is correct
18 Correct 20 ms 31032 KB Output is correct
19 Correct 18 ms 30972 KB Output is correct
20 Correct 19 ms 31056 KB Output is correct
21 Correct 16 ms 31052 KB Output is correct
22 Correct 21 ms 31032 KB Output is correct
23 Correct 15 ms 30968 KB Output is correct
24 Correct 18 ms 31060 KB Output is correct
25 Correct 24 ms 31064 KB Output is correct
26 Correct 23 ms 30992 KB Output is correct
27 Correct 23 ms 31028 KB Output is correct
28 Correct 16 ms 31068 KB Output is correct
29 Correct 17 ms 31064 KB Output is correct
30 Correct 20 ms 31052 KB Output is correct
31 Correct 23 ms 31060 KB Output is correct
32 Correct 22 ms 30968 KB Output is correct
33 Correct 25 ms 31052 KB Output is correct
34 Correct 20 ms 31060 KB Output is correct
35 Correct 25 ms 31052 KB Output is correct
36 Correct 23 ms 31052 KB Output is correct
37 Correct 17 ms 31004 KB Output is correct
38 Correct 19 ms 31060 KB Output is correct
39 Correct 22 ms 31052 KB Output is correct
40 Correct 22 ms 31052 KB Output is correct
41 Incorrect 17 ms 30840 KB Output isn't correct
42 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 95324 KB Output is correct
2 Correct 497 ms 78384 KB Output is correct
3 Correct 465 ms 78404 KB Output is correct
4 Correct 484 ms 78092 KB Output is correct
5 Correct 550 ms 95296 KB Output is correct
6 Correct 520 ms 95136 KB Output is correct
7 Correct 577 ms 95428 KB Output is correct
8 Correct 498 ms 95928 KB Output is correct
9 Correct 496 ms 78296 KB Output is correct
10 Correct 560 ms 95336 KB Output is correct
11 Correct 527 ms 95316 KB Output is correct
12 Correct 522 ms 95952 KB Output is correct
13 Correct 572 ms 96020 KB Output is correct
14 Incorrect 21 ms 30748 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 30796 KB Output is correct
2 Correct 21 ms 30900 KB Output is correct
3 Correct 17 ms 30808 KB Output is correct
4 Correct 19 ms 30812 KB Output is correct
5 Correct 16 ms 30788 KB Output is correct
6 Correct 16 ms 30796 KB Output is correct
7 Correct 18 ms 30924 KB Output is correct
8 Correct 21 ms 30848 KB Output is correct
9 Correct 17 ms 30868 KB Output is correct
10 Correct 17 ms 30796 KB Output is correct
11 Correct 22 ms 31052 KB Output is correct
12 Correct 20 ms 31036 KB Output is correct
13 Correct 19 ms 31064 KB Output is correct
14 Correct 16 ms 31060 KB Output is correct
15 Correct 24 ms 30960 KB Output is correct
16 Correct 19 ms 31044 KB Output is correct
17 Correct 18 ms 30996 KB Output is correct
18 Correct 20 ms 31032 KB Output is correct
19 Correct 18 ms 30972 KB Output is correct
20 Correct 19 ms 31056 KB Output is correct
21 Correct 16 ms 31052 KB Output is correct
22 Correct 21 ms 31032 KB Output is correct
23 Correct 15 ms 30968 KB Output is correct
24 Correct 18 ms 31060 KB Output is correct
25 Correct 24 ms 31064 KB Output is correct
26 Correct 23 ms 30992 KB Output is correct
27 Correct 23 ms 31028 KB Output is correct
28 Correct 16 ms 31068 KB Output is correct
29 Correct 17 ms 31064 KB Output is correct
30 Correct 20 ms 31052 KB Output is correct
31 Correct 23 ms 31060 KB Output is correct
32 Correct 22 ms 30968 KB Output is correct
33 Correct 25 ms 31052 KB Output is correct
34 Correct 20 ms 31060 KB Output is correct
35 Correct 25 ms 31052 KB Output is correct
36 Correct 23 ms 31052 KB Output is correct
37 Correct 17 ms 31004 KB Output is correct
38 Correct 19 ms 31060 KB Output is correct
39 Correct 22 ms 31052 KB Output is correct
40 Correct 22 ms 31052 KB Output is correct
41 Incorrect 17 ms 30840 KB Output isn't correct
42 Halted 0 ms 0 KB -