Submission #1182665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182665		william889	Tower (JOI24_tower)	C++20	25 / 100	239 ms	11792 KiB

Main

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

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back
typedef long long ll;
const ll mxN=2e5+5;
const ll mxM=1e12+5;
const ll inf=2e18;
ll n, Q, d, a, b;
pll tep[mxN];
pll v[mxN];
ll q[mxN];
ll f[mxN];
void solve(){
    memset(f, -1, sizeof(f));
    cin>>n>>Q>>d>>a>>b;
    for(ll i=0;i<n;i++){
        cin>>tep[i].F>>tep[i].S;
    }
    for(ll i=0;i<Q;i++){
        cin>>q[i];
    }
    v[0].F=0;
    v[0].S=tep[0].F-1;
    for(ll i=0;i<n-1;i++){
        v[i+1].F=tep[i].S+1;
        v[i+1].S=tep[i+1].F-1;
    }
    v[n].F=tep[n-1].S+1;
    v[n].S=mxM-1;
    f[0]=0;
    ll pt=0;
    for(ll i=1;i<=n;i++){
        while(pt<i && ((f[pt]==-1) || v[pt].S+d<v[i].F)){
            pt++;
        }
        if(f[pt]==-1) continue;
        if(f[pt]+d>v[i].S){
            continue;
        }
        if(v[i].F-d>=f[pt]){
            f[i]=v[i].F;
        }
        else{
            f[i]=f[pt]+d;
        }
    }
    for(ll i=0;i<Q;i++){
        ll lef=0, rig=n;
        ll good=-1;
        while(lef<=rig){
            ll mid=(lef+rig)/2;
            if(v[mid].F<=q[i]){
                good=mid;
                lef=mid+1;
            }
            else{
                rig=mid-1;
            }
        }
        assert(good!=-1);
        if(f[good]!=-1 && q[i]>=f[good] && q[i]<=v[good].S){
            cout<<q[i]<<'\n';
        }
        else{
            cout<<-1<<'\n';
        }
    }
}

int main(){
    
    solve();
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 38
• Subtask 3: 25 / 25
• Subtask 4: 0 / 32