Submission #1087855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087855		mychecksedad	Sprinklers (CEOI24_sprinklers)	C++17	9 / 100	484 ms	6572 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define en cout << '\n'
#define vi vector<int>
#define pii pair<int, int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
const int N = 1e5+100;


int n, m, a[N], b[N];
int dp[N][2], par[N][2];
int get(int l, int r){
	if(r < l) return 0;
	return upper_bound(b+1, b+1+m, r) - lower_bound(b+1, b+1+m, l);
}
int get_first(int l){
	int pos =	lower_bound(b+1, b+1+m, l) - b;
	if(pos == m+1) return 2e9;
	return b[pos]; 
}
void solve(){
	cin >> n >> m;
	vector<pii> v;
	for(int i = 1; i <= n; ++i){
		cin >> a[i];
		v.pb({a[i], 1});
	}
	for(int i = 1; i <= m; ++i){
		cin >> b[i];
		v.pb({b[i], 0});
	}
	sort(all(v));
	string soll;
	int l = 0, r = 1e9+2, ans = -1;
	while(l <= r){
		int k = l+r>>1;
		string sol = "";
		bool ok = 1;
		int last_covered = -2e9;
		dp[1][0] = get(-2e9, a[1] - k - 1) > 0 ? (int)(-2e9) : get_first(a[1] + 1);
		dp[1][1] = get(-2e9, a[1] - 1) > 0 ? (int)(-2e9) : get_first(a[1] + k + 1);
		for(int i = 2; i <= n ;++i){
			int L = a[i] - k, R = a[i];
			if(dp[i - 1][0] >= L){
				dp[i][0] = get_first(a[i] + 1);
				par[i][0] = 0;
			}else{
				dp[i][0] = -2e9;
			}

			if(dp[i - 1][0] >= a[i]){
				par[i][1] = 0;
				dp[i][1] = get_first(a[i] + k + 1);
			}else{
				dp[i][1] = dp[i - 1][0];
				par[i][1] = 0;
			}

			if(dp[i-1][1] >= L){
				if(dp[i][0] < get_first(a[i] + 1)){
					par[i][0] = 1;
				}
				dp[i][0] = max(dp[i][0], get_first(a[i] + 1));
			}else{
				dp[i][0] = max(dp[i][0], (int)(-2e9));
			}

			if(dp[i-1][1] >= a[i]){
				if(dp[i][1] < get_first(a[i] + k + 1)){
					par[i][1] = 1;
				}
				dp[i][1] = max(dp[i][1], get_first(a[i] + k + 1));
			}else{
				if(dp[i][1] < dp[i - 1][1]){
					dp[i][1] = dp[i - 1][1];
					par[i][1] = 1;
				}
			}
		}
		if(max(dp[n][0], dp[n][1]) == (int)2e9){
			ok = 1;
			int x = 0;
			if(dp[n][0] == 2e9) x = 0;
			else x = 1;
			sol += (x==0?'L':'R');
			for(int i = n - 1; i >= 1; --i){
				x = par[i + 1][x];
				sol += (x==0?'L':'R');
			}
			reverse(all(sol));	
		}
		else ok = 0;
		


		if(ok){
			ans = k;
			soll = sol;
			r = k - 1;
		}else{
			l = k + 1;
		}
	}

	cout << ans << '\n';
	if(ans != -1){
		cout << soll;
	}
}

int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	solve();
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:40:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |   int k = l+r>>1;
      |           ~^~
Main.cpp:47:22: warning: unused variable 'R' [-Wunused-variable]
   47 |    int L = a[i] - k, R = a[i];
      |                      ^
Main.cpp:43:7: warning: unused variable 'last_covered' [-Wunused-variable]
   43 |   int last_covered = -2e9;
      |       ^~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 0 / 17
• Subtask 4: 0 / 27
• Subtask 5: 0 / 47