Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* Author haleyk10198 */
- /* 作者: haleyk10198 */
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define MOD 1000000007
- #define LINF (1LL<<60)
- #define INF 2147483647
- #define PI 3.1415926535897932384626433
- #define ll long long
- #define pii pair<int,int>
- #define mp(x,y) make_pair((x),(y))
- using namespace std;
- using namespace __gnu_pbds;
- string itos(int x){
- stringstream ss;
- ss<<x;
- return ss.str();
- }
- //GREEDY?! NOT DP?! NO WAY, JUST WAITING FOR PRESTEST KO.
- //OK FFS IF I GOT SLAMMED DOWN CUZ FORGOT TO HANDLE <0 ... I... I...
- //OH GOSH EXCEPTIONS EXCEPTIONS EXCEPTIONS
- int len,n,p,t,cur,res,mx;
- map<int,int> dp;
- int main(){
- //freopen("input.txt","r",stdin);
- //freopen("output.txt","w",stdout);
- ios_base::sync_with_stdio(false);
- cin>>len>>n>>p>>t;
- dp[0]=0;
- for(int i=0,l,r;i<n;i++){
- cin>>l>>r;
- cur=dp.rbegin()->first;
- int tmp=dp[cur];
- cur=max(l,cur);
- tmp+=(r-cur)/p;
- cur=r-(r-cur)%p;
- if(--dp.upper_bound(cur+t)->second<tmp)
- dp[cur+t]=tmp;
- if(l-t<0)
- tmp=0;
- else
- tmp=--dp.upper_bound(l-t)->second;
- r-=(r-l)%p;
- tmp+=(r-l)/p;
- if((--dp.upper_bound(r+t))->second<tmp)
- dp[r+t]=tmp;
- }
- cout<<(dp.rbegin()->second)<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement