제출 #1140545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140545		hashimali	Sprinklers (CEOI24_sprinklers)	C++20	9 / 100	702 ms	7484 KiB

Main

#include <bits/stdc++.h>
#define endl '\n'
#define ld long double
#define pb push_back
#define pf push_front
#define mod 998244353
#define se second
#define fi first
#define all(ls) (ls).begin(),(ls).end()
#define int long long
using namespace std;
int n,m,works;
const int N=1e5+10;
int s[N],f[N],d[N];
void work(int mid){
    works=0;
    set<int>rem;
    for(int i=0;i<n;i++)
        d[i]=0;
    for(int i=0;i<m;i++)
        rem.insert(f[i]);
    for(int i=0;i<n;i++){
        if(rem.empty()){
            works=1;
            return;
        }
        int cur=*rem.begin();
        if(cur>=s[i])
            d[i]=1;
        else if(cur<(s[i]-mid)){
            works=0;
            return;
        }
        else if(cur>=(s[i]-mid))
            d[i]=0;
        else{
            auto up=rem.upper_bound(s[i]);
            if(up==rem.end())
                d[i]=0;
            else if(*up>=s[i+1])
                d[i]=0;
            else
                d[i]=1;
        }
        if(d[i]==0){
            //s[i]-mid....j....s[i]
            while(rem.size() and (s[i]-mid)<=*rem.begin() and *rem.begin()<=s[i])
                rem.erase(rem.begin());
        }
        if(d[i]==1){
            //s[i]....j....s[i]+mid
            auto ptr=rem.lower_bound(s[i]);
            while(rem.size() and ptr!=rem.end() and s[i]<=(*ptr) and (*ptr)<=(s[i]+mid))
                ptr=rem.erase(ptr);
        }
    }
    works=(rem.empty());
}
void solve(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>s[i];
    for(int i=0;i<m;i++)
        cin>>f[i];
    int low=0,high=1e14;
    while(low<=high){
        int mid=(low+high)/2;
        work(mid);
        if(works)
            high=mid-1;
        else
            low=mid+1;
    }
    if(low==(1e14+1))
        low=-1;
    cout<<low<<endl;
    if(low!=-1){
        work(low);
        for(int i=0;i<n;i++){
            if(d[i]==0)
                cout<<'L';
            else
                cout<<'R'; 
        }
        cout<<endl;
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    for(int i=1;i<=t;i++){
        // cout<<"Scenario #"<<i<<":"<<" ";
        solve();
    }
}

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