제출 #1087864

#제출 시각아이디문제언어결과실행 시간메모리
1087864mychecksedadSprinklers (CEOI24_sprinklers)C++17
100 / 100
558 ms6780 KiB
#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 ? b[1] : get_first(a[1] + 1);
		dp[1][1] = get(-2e9, a[1] - 1) > 0 ? b[1] : 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(max(a[i - 1] + k + 1, a[i] + 1))){
					par[i][0] = 1;
				}
				dp[i][0] = max(dp[i][0], get_first(max(a[i - 1] + k + 1, 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;
		
		// cout << k << '\n';
		// for(int i = 1; i <= n; ++i) cout << dp[i][0] << ' ' << dp[i][1] << '\n';

		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;
}

컴파일 시 표준 에러 (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;
      |       ^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...