zoj 3617 Riding Alone for Tho...

zoj 3617 Riding Alone for Tho...

#include<iostream>#include<cstdlib>#include<cstdio>#include<algorithm>#include<map>#include<stack>#include<queue>#include<cmath>#include<vector>#include<cstring>#include<string>#include<limits>#include<set>using namespace std;#define maxn 100010#define M 100010#define mod 1000000007#define pi acos(-1.0)#define inf (1LL<<60)#define lc n<<1#define rc n<<1|1typedef long long ll;ll x[M], a[M];pair<ll, ll> q[M];int main(){ ll hp; int n, h, t; while( scanf( "%d%lld", &n, &hp ) == 2 ){ h = t = 0; ll ans = 0, cur = hp; for( int i = 1; i <= n; ++i ){ scanf( "%lld%lld", x+i, a+i ); while( x[i] >= cur && t > h ){ ll res = q[h].first, rise = q[h].second; ll u = (x[i] - cur) / rise + 1; if( u * rise <= res ){ q[h].first -= u*rise; if( q[h].first == 0 ) ++h; ans += u; cur += u*rise; } else{ u = res / rise; ans += u; cur += u*rise; u = res % rise; ++h; if( h == t || u >= q[h].second ){ ++ans; cur += u; } else{ q[h].first += u; } } } cur -= x[i]; pair<ll, ll> p( x[i], a[i] ); while( t > h && a[i] >= q[t-1].second ){ --t; p.first += q[t].first; } q[t++] = p; } printf( "%lldn", ans ); }return 0;}