This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "railroad.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define all( x ) x.begin(), x.end()
#define umin( x, y ) x = min( x, (y) )
#define umax( x, y ) x = max( x, (y) )
#define pb push_back
using namespace std;
typedef long long Lint;
typedef pair<int,int> ii;
const int inf = 1e9 + 137;
const int maxn = 200020;
int a, n;
ii segment[maxn*3];
vector<ii> inc, de;
vector<int> s, ti;
ii find( int l, int r ) {
ii t = ii( inf, n+1 );
for(l+=n, r+=n;l<=r;l=(l+1)>>1, r=(r-1)>>1) {
if( l&1 ) umin( t, segment[l] );
if( ~r&1 ) umin( t, segment[r] );
}
return t;
}
Lint dn[1<<17][20];
int used[1<<17][20];
Lint f( int n, int last ) {
if( n == (1<<a)-1 ) return 0;
if( used[n][last] ) return dn[n][last];
used[n][last] = 1;
Lint now = ti[last];
Lint ret = 1e18;
for(int i=0;i<a;i++)
if( !((1<<i)&n) ) {
umin( ret, f( n|(1<<i), i ) + max( 0ll, now-s[i] ) );
}
return dn[n][last] = ret;
}
bool comp( const ii &a, const ii &b ) {
return a.se < b.se;
}
Lint plan_roller_coaster(vector<int> S, vector<int> Ti) {
s = S;
ti = Ti;
a = s.size();
/*if( s.size() < 17 ) {
ti.pb( 1 );
return f( 0, a );
}*/
for(int i=0;i<a;i++) {
if( s[i] > ti[i] ) de.pb( ii( ti[i], s[i] ) );
else inc.pb( ii( s[i], ti[i] ) );
}
sort( all( inc ), comp );
sort( all( de ), comp );
n = 1;
while( n < inc.size() ) n <<= 1;
for(int i=1;i<n+n;i++)
segment[i] = ii( inf, n+1 );
for(int i=0;i<inc.size();i++)
segment[i+n] = ii( inc[i].se, i );
for(int i=n-1;i>=1;i--)
segment[i] = min( segment[i+i], segment[i+i+1] );
multiset<ii> st;
int now = 1;
for(int i=0,j=0;i<de.size();i++) {
//printf("asd\n");
while( j < inc.size() && inc[j].se <= de[i].se ) {
st.insert( inc[j] );
j++;
}
int last = de[i].se;
int go = now;
while( 1 ) {
multiset<ii> :: iterator it = st.lower_bound( ii( go, 0 ) );
//printf("--- %d %d -- %d %d\n",it->fi,it->se,go,n-1);
if( it != st.end() && it->se <= last ) {
ii t = *it;
st.erase( it );
go = t.se;
} else break;
}
now = de[i].fi;
}
while( 1 ) {
multiset<ii> :: iterator it = st.lower_bound( ii( now, 0 ) );
if( it != st.end() ) {
ii t = *it;
st.erase( it );
now = t.se;
} else break;
}
if( st.size() == 0 ) return 0;
return 1;
}
Compilation message (stderr)
railroad.cpp: In function 'Lint plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:71:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while( n < inc.size() ) n <<= 1;
^
railroad.cpp:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<inc.size();i++)
^
railroad.cpp:84:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0,j=0;i<de.size();i++) {
^
railroad.cpp:86:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while( j < inc.size() && inc[j].se <= de[i].se ) {
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |