Submission #624805

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
624805	2022-08-08T18:42:12 Z	CSQ31	Abduction 2 (JOI17_abduction2)	C++17	100 / 100	729 ms	139888 KB

abduction2

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int,int> pii;
typedef long long int ll;
const int MAXN = 5e4+5;
vector<int>a,b;
int h,w,q;
map<int,ll>dp[2][MAXN];
int lg[MAXN];
struct spt{
	vector<int>a;
	vector<vector<int>>mx;
	int n;
	spt(){}
	spt(vector<int>_a){
		a = _a;
		n = a.size();
		mx.resize(20);
		for(int i=0;i<20;i++)mx[i].assign(n,-1e9);
		for(int i=0;i<n;i++)mx[0][i] = a[i];
		for(int i=1;i<20;i++){
			for(int j=0;j+(1<<i)-1<n;j++){
				mx[i][j] = max(mx[i-1][j],mx[i-1][j+(1<<(i-1))]);
			}
		}
	}
	int query(int l,int r){
		int v = lg[r-l+1];
		int res = max(mx[v][l],mx[v][r-(1<<v)+1]);
		return res;
	}
	void print(){
		for(int i=0;i<20;i++){
			for(int j=0;j+(1<<i)-1<n;j++)cout<<mx[i][j]<<" ";
			cout<<'\n';
		}
		
		
	}
}mw,mh;
ll solve(ll i,ll j,ll k){
	if(dp[k][i].find(j) != dp[k][i].end())return dp[k][i][j];
	if(!k){
		dp[0][i][j] = -1e9;
	    ll l = j+1,r = w-1;
		while(r>=l){
			ll mid = (l+r)/2;
			if(mw.query(j+1,mid) > a[i])r=mid-1;
			else l = mid+1;
		}
		if(l<w)dp[0][i][j] = max(dp[0][i][j],solve(i,l,1) + l - j);
		else dp[0][i][j] = max(dp[0][i][j],w-1-j);
		l = 0;
		r = j-1;
		while(r>=l){
			ll mid = (l+r)/2;
			if(mw.query(mid,j-1) > a[i])l = mid+1;
			else r = mid-1;
		}
		if(r>=0)dp[0][i][j] = max(dp[0][i][j],solve(i,r,1) + j - r);
		else dp[0][i][j] = max(dp[0][i][j],j);
	}else{
		dp[1][i][j] = -1e9;
		ll l = i+1,r = h-1;
		while(r>=l){
			ll mid = (l+r)/2;
			if(mh.query(i+1,mid) > b[j])r=mid-1;
			else l = mid+1;
		}
		if(l<h)dp[1][i][j] = max(dp[1][i][j],solve(l,j,0) + l - i);
		else dp[1][i][j] = max(dp[1][i][j],l-1-i);
		l = 0;
		r = i-1;
		while(r>=l){
			ll mid = (l+r)/2;
			if(mh.query(mid,i-1) > b[j])l = mid+1;
			else r = mid-1;
		}
		if(r>=0)dp[1][i][j] = max(dp[1][i][j],solve(r,j,0) + i - r);
		else dp[1][i][j] = max(dp[1][i][j],i);
	}
	return dp[k][i][j];
}
int main()
{
	owo
	cin>>h>>w>>q;
	a.resize(h);
	b.resize(w);
	for(int i=0;i<h;i++)cin>>a[i];
	for(int i=0;i<w;i++)cin>>b[i];
	lg[1] = 0;
	for(int i=2;i<=50000;i++)lg[i] = lg[i/2]+1;
	mh = spt(a);
	mw = spt(b);
	//mh.print();
	//mw.print();
	while(q--){
		int i,j;
		cin>>i>>j;
		i--;
		j--;
		ll ans = max(solve(i,j,0),solve(i,j,1));
		cout<<ans<<'\n';
	}
	
}

Subtask #1
13.0 / 13.0

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

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5204 KB	Output is correct
2	Correct	3 ms	5204 KB	Output is correct
3	Correct	3 ms	5204 KB	Output is correct
4	Correct	3 ms	5204 KB	Output is correct
5	Correct	3 ms	5204 KB	Output is correct
6	Correct	2 ms	5204 KB	Output is correct
7	Correct	3 ms	5204 KB	Output is correct
8	Correct	4 ms	5204 KB	Output is correct
9	Correct	3 ms	5204 KB	Output is correct
10	Correct	4 ms	5204 KB	Output is correct
11	Correct	3 ms	5204 KB	Output is correct
12	Correct	3 ms	5460 KB	Output is correct
13	Correct	4 ms	5528 KB	Output is correct
14	Correct	3 ms	5460 KB	Output is correct
15	Correct	3 ms	5460 KB	Output is correct
16	Correct	3 ms	5460 KB	Output is correct
17	Correct	4 ms	5544 KB	Output is correct
18	Correct	3 ms	5588 KB	Output is correct
19	Correct	4 ms	5716 KB	Output is correct
20	Correct	4 ms	5844 KB	Output is correct
21	Correct	4 ms	5716 KB	Output is correct
22	Correct	4 ms	5972 KB	Output is correct

Subtask #3
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5204 KB	Output is correct
2	Correct	3 ms	5204 KB	Output is correct
3	Correct	3 ms	5204 KB	Output is correct
4	Correct	3 ms	5204 KB	Output is correct
5	Correct	3 ms	5204 KB	Output is correct
6	Correct	2 ms	5204 KB	Output is correct
7	Correct	3 ms	5204 KB	Output is correct
8	Correct	4 ms	5204 KB	Output is correct
9	Correct	3 ms	5204 KB	Output is correct
10	Correct	4 ms	5204 KB	Output is correct
11	Correct	3 ms	5204 KB	Output is correct
12	Correct	3 ms	5460 KB	Output is correct
13	Correct	4 ms	5528 KB	Output is correct
14	Correct	3 ms	5460 KB	Output is correct
15	Correct	3 ms	5460 KB	Output is correct
16	Correct	3 ms	5460 KB	Output is correct
17	Correct	4 ms	5544 KB	Output is correct
18	Correct	3 ms	5588 KB	Output is correct
19	Correct	4 ms	5716 KB	Output is correct
20	Correct	4 ms	5844 KB	Output is correct
21	Correct	4 ms	5716 KB	Output is correct
22	Correct	4 ms	5972 KB	Output is correct
23	Correct	17 ms	14056 KB	Output is correct
24	Correct	17 ms	13932 KB	Output is correct
25	Correct	17 ms	13968 KB	Output is correct
26	Correct	17 ms	13936 KB	Output is correct
27	Correct	18 ms	13968 KB	Output is correct
28	Correct	25 ms	19432 KB	Output is correct
29	Correct	18 ms	14576 KB	Output is correct
30	Correct	41 ms	20320 KB	Output is correct
31	Correct	56 ms	22136 KB	Output is correct
32	Correct	19 ms	14060 KB	Output is correct
33	Correct	23 ms	15848 KB	Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
56.0 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5204 KB	Output is correct
2	Correct	3 ms	5204 KB	Output is correct
3	Correct	3 ms	5204 KB	Output is correct
4	Correct	3 ms	5204 KB	Output is correct
5	Correct	3 ms	5204 KB	Output is correct
6	Correct	2 ms	5204 KB	Output is correct
7	Correct	3 ms	5204 KB	Output is correct
8	Correct	4 ms	5204 KB	Output is correct
9	Correct	3 ms	5204 KB	Output is correct
10	Correct	4 ms	5204 KB	Output is correct
11	Correct	3 ms	5204 KB	Output is correct
12	Correct	3 ms	5460 KB	Output is correct
13	Correct	4 ms	5528 KB	Output is correct
14	Correct	3 ms	5460 KB	Output is correct
15	Correct	3 ms	5460 KB	Output is correct
16	Correct	3 ms	5460 KB	Output is correct
17	Correct	4 ms	5544 KB	Output is correct
18	Correct	3 ms	5588 KB	Output is correct
19	Correct	4 ms	5716 KB	Output is correct
20	Correct	4 ms	5844 KB	Output is correct
21	Correct	4 ms	5716 KB	Output is correct
22	Correct	4 ms	5972 KB	Output is correct
23	Correct	17 ms	14056 KB	Output is correct
24	Correct	17 ms	13932 KB	Output is correct
25	Correct	17 ms	13968 KB	Output is correct
26	Correct	17 ms	13936 KB	Output is correct
27	Correct	18 ms	13968 KB	Output is correct
28	Correct	25 ms	19432 KB	Output is correct
29	Correct	18 ms	14576 KB	Output is correct
30	Correct	41 ms	20320 KB	Output is correct
31	Correct	56 ms	22136 KB	Output is correct
32	Correct	19 ms	14060 KB	Output is correct
33	Correct	23 ms	15848 KB	Output is correct
34	Correct	4 ms	5716 KB	Output is correct
35	Correct	4 ms	5716 KB	Output is correct
36	Correct	4 ms	5716 KB	Output is correct
37	Correct	4 ms	5648 KB	Output is correct
38	Correct	4 ms	5716 KB	Output is correct
39	Correct	3 ms	5844 KB	Output is correct
40	Correct	3 ms	5716 KB	Output is correct
41	Correct	5 ms	5972 KB	Output is correct
42	Correct	5 ms	5972 KB	Output is correct
43	Correct	5 ms	5972 KB	Output is correct
44	Correct	5 ms	6100 KB	Output is correct
45	Correct	24 ms	14100 KB	Output is correct
46	Correct	19 ms	14064 KB	Output is correct
47	Correct	21 ms	14096 KB	Output is correct
48	Correct	23 ms	14076 KB	Output is correct
49	Correct	25 ms	14984 KB	Output is correct
50	Correct	30 ms	19664 KB	Output is correct
51	Correct	29 ms	20324 KB	Output is correct
52	Correct	62 ms	25240 KB	Output is correct
53	Correct	60 ms	24732 KB	Output is correct
54	Correct	61 ms	24368 KB	Output is correct
55	Correct	82 ms	29620 KB	Output is correct
56	Correct	729 ms	139888 KB	Output is correct
57	Correct	225 ms	47112 KB	Output is correct
58	Correct	160 ms	45532 KB	Output is correct
59	Correct	159 ms	45292 KB	Output is correct

Submission #624805

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 10.0 / 10.0

Subtask #3 17.0 / 17.0

Subtask #4 4.0 / 4.0

Subtask #5 56.0 / 56.0

Subtask #1
13.0 / 13.0

Subtask #2
10.0 / 10.0

Subtask #3
17.0 / 17.0

Subtask #4
4.0 / 4.0

Subtask #5
56.0 / 56.0