oj.uz

Submission #1080193

# Submission time Handle Problem Language Result Execution time Memory
1080193 2024-08-29T07:54:06 Z LCJLY Abduction 2 (JOI17_abduction2) C++14
27 / 100
 267 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

void solve(){ 	
	int n,m,q;
	cin >> n >> m >> q;
	
	int hori[n];
	vector<pair<int,pii>>v; //val index row/column
	for(int x=0;x<n;x++){
		cin >> hori[x];
		v.push_back({hori[x],{x,0}});
	}
	
	int vert[m];
	for(int x=0;x<m;x++){
		cin >> vert[x];
		v.push_back({vert[x],{x,1}});
	}
	
	sort(v.begin(),v.end());
	reverse(v.begin(),v.end());
	int ans[n][m];
	memset(ans,-1,sizeof(ans));
	bool done[n][m];
	memset(done,0,sizeof(done));
	for(int x=0;x<n+m;x++){
		pair<int,pii>cur=v[x];
		if(cur.second.second==0){
			//hori
			int index=cur.second.first;
			
			int hold=-1;
			for(int y=0;y<m;y++){				
				if(done[index][y]==1){
					hold=ans[index][y];
				}
				else hold++;
				ans[index][y]=max(ans[index][y],hold);
			}	
			
			hold=-1;
			for(int y=m-1;y>=0;y--){
				if(done[index][y]==1){
					hold=ans[index][y];
				}
				else hold++;
				done[index][y]=true;
				ans[index][y]=max(ans[index][y],hold);
			}
		}
		else{
			//vert
			int index=cur.second.first;
			
			int hold=-1;
			for(int y=0;y<n;y++){
				if(done[y][index]==1){
					hold=ans[y][index];
				}
				else hold++;
				ans[y][index]=max(ans[y][index],hold);
			}
			
			hold=-1;
			for(int y=n-1;y>=0;y--){
				if(done[y][index]==1){
					hold=ans[y][index];
				}
				else hold++;
				done[y][index]=true;
				ans[y][index]=max(ans[y][index],hold);
			}
		}
	}
	
	int up[n][m];
	int down[n][m];
	int lft[n][m];
	int rgt[n][m];
	memset(up,-1,sizeof(up));
	memset(down,-1,sizeof(down));
	memset(lft,-1,sizeof(lft));
	memset(rgt,-1,sizeof(rgt));
	
	for(int y=0;y<m;y++){
		int cur=-1;
		for(int x=0;x<n;x++){
			up[x][y]=cur;
			if(hori[x]>vert[y]) cur=x;
		}
		
		cur=-1;
		for(int x=n-1;x>=0;x--){
			down[x][y]=cur;
			if(hori[x]>vert[y]) cur=x;
		}
	}
	
	for(int x=0;x<n;x++){
		int cur=-1;
		for(int y=0;y<m;y++){
			lft[x][y]=cur;
			if(vert[y]>hori[x]) cur=y;
		}
		
		cur=-1;
		for(int y=m-1;y>=0;y--){
			rgt[x][y]=cur;
			if(vert[y]>hori[x]) cur=y;
		}
	}	
	
	//for(int x=0;x<n;x++){
		//for(int y=0;y<m;y++){
			//cout << ans[x][y] <<  " ";
		//}
		//cout << "\n";
	//}
	
	int temp,temp2;
	for(int x=0;x<q;x++){
		cin >> temp >> temp2;
		temp--; temp2--;
		//up
		int take=0;
		if(up[temp][temp2]==-1) take=max(take,temp);
		else{
			int index=up[temp][temp2];
			take=max(take,ans[index][temp2]+abs(index-temp));
		}
		
		if(down[temp][temp2]==-1) take=max(take,n-1-temp);
		else{
			int index=down[temp][temp2];
			take=max(take,ans[index][temp2]+abs(index-temp));
		}
		
		if(lft[temp][temp2]==-1) take=max(take,temp2);
		else{
			int index=lft[temp][temp2];
			take=max(take,ans[temp][index]+abs(index-temp2));
		}
		
		if(rgt[temp][temp2]==-1) take=max(take,m-1-temp2);
		else{
			int index=rgt[temp][temp2];
			take=max(take,ans[temp][index]+abs(index-temp2));
		}
		
		take=max(take,ans[temp][temp2]);
		
		cout << take << "\n";
	}
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	//freopen("in.txt","r",stdin);
	while(t--){
		solve();
	}
}

Subtask #1
13.0 / 13.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 168 ms 161104 KB Output is correct
13 Correct 169 ms 161116 KB Output is correct
14 Correct 177 ms 161124 KB Output is correct
15 Correct 167 ms 161088 KB Output is correct
16 Correct 175 ms 161104 KB Output is correct
17 Correct 158 ms 161360 KB Output is correct
18 Correct 153 ms 161116 KB Output is correct
19 Correct 158 ms 161104 KB Output is correct
20 Correct 155 ms 156244 KB Output is correct
21 Correct 158 ms 158032 KB Output is correct
22 Correct 162 ms 161360 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 168 ms 161104 KB Output is correct
13 Correct 169 ms 161116 KB Output is correct
14 Correct 177 ms 161124 KB Output is correct
15 Correct 167 ms 161088 KB Output is correct
16 Correct 175 ms 161104 KB Output is correct
17 Correct 158 ms 161360 KB Output is correct
18 Correct 153 ms 161116 KB Output is correct
19 Correct 158 ms 161104 KB Output is correct
20 Correct 155 ms 156244 KB Output is correct
21 Correct 158 ms 158032 KB Output is correct
22 Correct 162 ms 161360 KB Output is correct
23 Runtime error 267 ms 524288 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 161100 KB Output is correct
2 Correct 174 ms 161104 KB Output is correct
3 Correct 186 ms 161032 KB Output is correct
4 Correct 184 ms 161108 KB Output is correct
5 Correct 176 ms 161108 KB Output is correct
6 Correct 156 ms 161104 KB Output is correct
7 Correct 184 ms 161020 KB Output is correct
8 Correct 162 ms 161104 KB Output is correct
9 Correct 156 ms 158408 KB Output is correct
10 Correct 168 ms 160156 KB Output is correct
11 Correct 157 ms 161104 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 168 ms 161104 KB Output is correct
13 Correct 169 ms 161116 KB Output is correct
14 Correct 177 ms 161124 KB Output is correct
15 Correct 167 ms 161088 KB Output is correct
16 Correct 175 ms 161104 KB Output is correct
17 Correct 158 ms 161360 KB Output is correct
18 Correct 153 ms 161116 KB Output is correct
19 Correct 158 ms 161104 KB Output is correct
20 Correct 155 ms 156244 KB Output is correct
21 Correct 158 ms 158032 KB Output is correct
22 Correct 162 ms 161360 KB Output is correct
23 Runtime error 267 ms 524288 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -