oj.uz

Submission #330633

# Submission time Handle Problem Language Result Execution time Memory
330633 2020-11-26T02:35:44 Z YJU Abduction 2 (JOI17_abduction2) C++14
13 / 100
 3 ms 1772 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e3+5;
const ll K=350;
const ld pi=3.14159265359;
const ll INF=(1LL<<40);
const ll lgn=18;
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll ad[lgn+1][N],au[lgn+1][N],bl[lgn+1][N],br[lgn+1][N];
ll a[N],b[N],n,m,q;
map<ll,map<ll,map<ll,ll> > > dp;

ll f(ll y,ll x,ll dr){
	if(dp[y][x].find(dr)!=dp[y][x].end()){return dp[y][x][dr];}
	
	
	if(dr==0){
		ll Y=y;
		for(int i=lgn;i>=0;i--){
			if(Y>(1LL<<i)&&au[i][Y]<b[x])Y-=(1LL<<i);
		}
		Y--;
		if(Y==0)return y-Y-1;
		if(a[Y]<b[x])return y-Y;
		return dp[y][x][dr]=y-Y+max(f(Y,x,1),f(Y,x,3));
	}else if(dr==1){
		ll X=x;
		for(int i=lgn;i>=0;i--){
			if(X>(1LL<<i)&&bl[i][X]<a[y])X-=(1LL<<i);
		}
		X--;
		if(X==0)return x-X-1;
		if(b[X]<a[y])return x-X;
		return dp[y][x][dr]=x-X+max(f(y,X,0),f(y,X,2));
	}else if(dr==2){
		ll Y=y;
		for(int i=lgn;i>=0;i--){
			if(Y+(1LL<<i)<=n&&ad[i][Y]<b[x])Y+=(1LL<<i);
		}
		Y++;
		if(Y==n+1)return Y-y-1;
		if(a[Y]<b[x])return Y-y;
		return dp[y][x][dr]=Y-y+max(f(Y,x,1),f(Y,x,3));
	}else if(dr==3){
		ll X=x;
		for(int i=lgn;i>=0;i--){
			if(X+(1LL<<i)<=m&&br[i][X]<a[y])X+=(1LL<<i);
		}
		X++;
		if(X==m+1)return X-x-1;
		if(b[X]<a[y])return X-x;
		return dp[y][x][dr]=X-x+max(f(y,X,0),f(y,X,2));
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m>>q;
	REP1(i,n)cin>>a[i];
	REP1(i,m)cin>>b[i];
	REP1(i,n)au[0][i]=a[i-1],ad[0][i]=a[i+1];
	REP1(i,m)br[0][i]=b[i+1],bl[0][i]=b[i-1];
	for(int i=0;i<lgn;i++){
		REP1(j,n){
			au[i+1][j]=max(au[i][j],au[i][max(2LL,j-(1LL<<i))]);
			ad[i+1][j]=max(ad[i][j],ad[i][min(n-1,j+(1LL<<i))]);
		}
		REP1(j,m){
			br[i+1][j]=max(br[i][j],br[i][min(m-1,j+(1LL<<i))]);
			bl[i+1][j]=max(bl[i][j],bl[i][max(2LL,j-(1LL<<i))]);
		}
	}
	ll tmpa,tmpb;
	while(q--){
		cin>>tmpa>>tmpb;
		cout<<max(max(f(tmpa,tmpb,0),f(tmpa,tmpb,1)),max(f(tmpa,tmpb,2),f(tmpa,tmpb,3)))<<"\n";
	}
	return 0;
}

Compilation message

abduction2.cpp: In function 'll f(ll, ll, ll)':
abduction2.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
   68 | }
      | ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Runtime error 3 ms 1772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Runtime error 3 ms 1772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

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

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Runtime error 3 ms 1772 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -