Submission #377339

#	Time	Username	Problem	Language	Result	Execution time	Memory
377339		rrrr10000	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	148 ms	24684 KiB

railroad

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define rosrt(a) {sort(all(a));reverse(all(a));}
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];};cout<<'\n';}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
template<class T> void outp(T p){cout<<'('<<p.fi<<','<<p.se<<')'<<endl;}
template<class T> void outvp(T v){for(auto x:v)cout<<'('<<x.fi<<','<<x.se<<')';cout<<endl;}
#include "railroad.h"
ll plan_roller_coaster(vector<int> s,vector<int> t){
    ll n=s.size();
    vp srts(n),srtt(n);
    rep(i,n)srts[i]=P(s[i],i);
    rep(i,n)srtt[i]=P(t[i],i);
    sort(all(srts));sort(all(srtt));
    vvi done(n,vi(2));
    if(srts[0].se!=srtt[n-1].se){
        done[srts[0].se][0]=1;
        done[srtt[n-1].se][1]=1;
    }
    else if(srtt[n-1].fi-srts[1].fi>=srtt[n-2].fi-srts[0].fi){
        done[srts[1].se][0]=1;
        done[srtt[n-1].se][1]=1;
    }
    else{
        done[srts[0].se][0]=1;
        done[srtt[n-2].se][1]=1;
    }
    // outvv(done);
    ll a=n-1,b=n-1,c=n-1,d=n-1,ans=0;
    while(a!=-1&&b!=-1){
        // outp(P(a,b));
        if(srtt[b].fi>=srts[a].fi){
            ll i=srtt[b].se,k=srtt[b].fi;b--;
            if(done[i][1])continue;
            done[i][1]=true;
            if(!done[i][0]){
                while(done[srts[a].se][0])a--;
                ans+=max(0ll,k-srts[a].fi);
                done[srts[a].se][0]=true;
            }
            else{
                while(c!=-1&&(done[srts[c].se][0]||done[srts[c].se][1]))c--;
                if(c==-1){
                    done[i][1]=false;break;
                }
                ans+=max(0ll,k-srts[c].fi);
                done[srts[c].se][0]=true;
            }
        }
        else{
            ll i=srts[a].se,k=srts[a].fi;a--;
            if(done[i][0])continue;
            done[i][0]=true;
            if(!done[i][1]){
                while(done[srtt[b].se][1])b--;
                ans+=max(0ll,srtt[b].fi-k);
                done[srtt[b].se][1]=true;
            }
            else{
                while(d!=-1&&(done[srtt[d].se][0]||done[srtt[d].se][1]))d--;
                if(d==-1){
                    done[i][0]=false;break;
                }
                ans+=max(0ll,srtt[d].fi-k);
                done[srtt[d].se][1]=true;
            }
        }
    }
    // outvv(done);
    P p=P(-1,-1);
    rep(i,n)if(!done[i][0])p.fi=i;
    rep(i,n)if(!done[i][1])p.se=i;
    if(p.fi!=-1){
        ans+=max(0,t[p.se]-s[p.fi]);
    }
    return ans;
}
/*
int main(){
    ll n;cin>>n;
    vector<int> s(n),t(n);
    rep(i,n)cin>>s[i];
    rep(i,n)cin>>t[i];
    out(plan_roller_coaster(s,t));
}*/

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36