Advertisement
Guest User

Untitled

a guest
Sep 30th, 2016
181
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.27 KB | None | 0 0
  1. /* Author haleyk10198 */
  2. /* 作者: haleyk10198 */
  3. #include <bits/stdc++.h>
  4. #include <ext/pb_ds/assoc_container.hpp>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6.  
  7. #define MOD 1000000007
  8. #define LINF (1LL<<60)
  9. #define INF 2147483647
  10. #define PI 3.1415926535897932384626433
  11. #define ll long long
  12. #define pii pair<int,int>
  13. #define mp(x,y) make_pair((x),(y))
  14.  
  15. using namespace std;
  16. using namespace __gnu_pbds;
  17.  
  18. string itos(int x){
  19. stringstream ss;
  20. ss<<x;
  21. return ss.str();
  22. }
  23.  
  24. //GREEDY?! NOT DP?! NO WAY, JUST WAITING FOR PRESTEST KO.
  25. //OK FFS IF I GOT SLAMMED DOWN CUZ FORGOT TO HANDLE <0 ... I... I...
  26.  
  27. //OH GOSH EXCEPTIONS EXCEPTIONS EXCEPTIONS
  28.  
  29. int len,n,p,t,cur,res,mx;
  30.  
  31. map<int,int> dp;
  32.  
  33. int main(){
  34. //freopen("input.txt","r",stdin);
  35. //freopen("output.txt","w",stdout);
  36. ios_base::sync_with_stdio(false);
  37. cin>>len>>n>>p>>t;
  38. dp[0]=0;
  39. for(int i=0,l,r;i<n;i++){
  40. cin>>l>>r;
  41. cur=dp.rbegin()->first;
  42. int tmp=dp[cur];
  43. cur=max(l,cur);
  44. tmp+=(r-cur)/p;
  45. cur=r-(r-cur)%p;
  46. if(--dp.upper_bound(cur+t)->second<tmp)
  47. dp[cur+t]=tmp;
  48. if(l-t<0)
  49. tmp=0;
  50. else
  51. tmp=--dp.upper_bound(l-t)->second;
  52. r-=(r-l)%p;
  53. tmp+=(r-l)/p;
  54. if((--dp.upper_bound(r+t))->second<tmp)
  55. dp[r+t]=tmp;
  56. }
  57. cout<<(dp.rbegin()->second)<<endl;
  58. return 0;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement