Submission #698417

#	Time	Username	Problem	Language	Result	Execution time	Memory
698417		amunduzbaev	Abduction 2 (JOI17_abduction2)	C++17	100 / 100	1495 ms	22084 KiB

abduction2

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
//~ #define int ll

const int N = 5e4 + 5;
const int M = 16;
vector<pair<int, ll>> tot[N + N];
int a[2][N], pos[2][N];
int L[2][N][M], R[2][N][M];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	ar<int, 2> n; int q; 
	cin >> n[0] >> n[1] >> q;
	
	for(int t=0;t<2;t++){
		a[t][0] = a[t][n[t] + 1] = 2e9;
		for(int i=1;i<=n[t];i++){
			cin >> a[t][i];
		}
		
		vector<int> ss; ss.push_back(0);
		for(int i=1;i<=n[t];i++){
			while(!ss.empty() && a[t][ss.back()] < a[t][i]){
				ss.pop_back();
			}
			
			L[t][i][0] = ss.back();
			ss.push_back(i);
		}
		
		ss.clear(); ss.push_back(n[t] + 1);
		for(int i=n[t];i>0;i--){
			while(!ss.empty() && a[t][ss.back()] < a[t][i]){
				ss.pop_back();
			}
			
			R[t][i][0] = ss.back();
			ss.push_back(i);
		}
		L[t][0][0] = 0;
		R[t][n[t] + 1][0] = n[t] + 1;
		for(int j=1;j<M;j++){
			for(int i=0;i<=n[t]+1;i++){
				L[t][i][j] = L[t][L[t][i][j-1]][j-1];
				R[t][i][j] = R[t][R[t][i][j-1]][j-1];
			}
		}
	}
	vector<ar<int, 2>> p;
	for(int t=0;t<2;t++){
		for(int i=1;i<=n[t];i++){
			p.push_back({t, i});
		}
	}
	sort(p.begin(), p.end(), [&](auto i, auto j){
		return a[i[0]][i[1]] < a[j[0]][j[1]];
	});
	for(int i=0;i<(int)p.size();i++){
		pos[p[i][0]][p[i][1]] = i;
	}
	
	auto solve = [&](int i, int j){
		//~ memset(d, 0, sizeof d);
		if(a[0][i] > a[1][j]){
			tot[pos[0][i]].push_back({j, 0});
		} else {
			tot[pos[1][j]].push_back({i, 0});
		}
		
		ll res = 0;
		for(auto [t, i] : p){
			if(tot[pos[t][i]].empty()) continue;
			int c = t ^ 1;
			vector<pair<int, ll>>& v = tot[pos[t][i]];
			sort(v.begin(), v.end());
			ll L = 0, R = 0;
			int l = v[0].first, r = v.back().first;
			//~ cout<<l<<" "<<r<<"\n";
			for(int j=M-1;~j;j--){
				if(a[c][::L[c][l][j]] < a[t][i]) l = ::L[c][l][j];
				if(a[c][::R[c][r][j]] < a[t][i]) r = ::R[c][r][j];
			}
			//~ cout<<l<<" "<<r<<"\n";
			l = ::L[c][l][0];
			r = ::R[c][r][0];
			for(auto [j, d] : v){
				//~ cout<<t<<" "<<i<<" "<<j<<" "<<d<<"\n";
				L = max(L, d + abs(j - l));
				R = max(R, d + abs(j - r));
			}
			//~ cout<<i<<" "<<l<<" "<<r<<"\n";
			if(l){
				tot[pos[c][l]].push_back({i, L});
			} else {
				res = max(res, L - 1);
			}
			
			if(r <= n[c]){
				tot[pos[c][r]].push_back({i, R});
			} else {
				res = max(res, R - 1);
			}
			v.clear();
		}
		//~ cout<<i<<" "<<j<<" "<<res<<"\n";
		return res;
	};
	
	auto Answer = [&](int i, int j){
		ll res = max(res, solve(i, j));
		if(a[0][i] < a[1][j]){
			int c = 1, t = 0;
			int l = j - 1, r = j + 1;
			while(l && a[c][l] < a[t][i]) l--;
			while(r <= n[c] && a[c][r] < a[t][i]) r++;
			
			if(l) res = max(res, solve(i, l) + abs(j - l));
			else res = max(res, 1ll * j - 1);
			
			if(r <= n[c]) res = max(res, solve(i, r) + abs(r - j));
			else res = max(res, 1ll * n[c] - j);
		}
		else { swap(i, j);
			int c = 0, t = 1;
			int l = j - 1, r = j + 1;
			while(l && a[c][l] < a[t][i]) l--;
			while(r <= n[c] && a[c][r] < a[t][i]) r++;
			
			if(l) res = max(res, solve(l, i) + abs(j - l));
			else res = max(res, 1ll * j - 1);
			
			if(r <= n[c]) res = max(res, solve(r, i) + abs(r - j));
			else res = max(res, 1ll * n[c] - j);
		}
		
		return res;
	};
	
	while(q--){
		int i, j; cin >> i >> j;
		cout<<Answer(i, j)<<"\n";
	}
}

Compilation message (stderr)

abduction2.cpp: In function 'int main()':
abduction2.cpp:115:6: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |   ll res = max(res, solve(i, j));
      |      ^~~

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 4 / 4
• Subtask 5: 56 / 56