Advertisement
Guest User

Untitled

a guest
Oct 24th, 2011
180
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.86 KB | None | 0 0
  1. #include <sstream>
  2. #include <queue>
  3. #include <set>
  4. #include <map>
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <cstdlib>
  8. #include <cctype>
  9. #include <cmath>
  10. #include <iostream>
  11. #include <string>
  12. #include <vector>
  13. #include <algorithm>
  14.  
  15. using namespace std;
  16.  
  17. #define INF                  (1<<30)
  18. #define LINF                 ((long long)1<<60)
  19. #define PI                   2*acos(0)
  20. #define eps                  1e-7
  21. #define two(x)               (1<<x)
  22. #define twoL(x)              ((long long)1<<x)
  23.  
  24. #define FOR(i,a,b)           for(i=(a);i<(b);i++)
  25. #define FORD(i,a,b)          for(i=(a);i>(b);i--)
  26. #define REP(i,n)             for(i=0;i<(n);i++)
  27. #define REV(i,n)             for(i=(n-1);i>=0;i--)
  28. #define Sort(s)              sort(s.begin(),s.end())
  29. #define ASort(s,n)           sort(&s[0],&s[n])
  30. #define Reverse(s)           reverse(s.begin(),s.end())
  31. #define Mem(A,c)             memset(A,c,sizeof(A))
  32. #define Split(str)           {vs.clear();istringstream A(str);while(A>>(str))vs.push_back(str);}
  33. #define CLR(s)               s.clear()
  34. #define SZ(s)                s.size()
  35. #define pb                   push_back
  36. #define mp                   make_pair
  37. #define fs                   first
  38. #define sc                   second
  39.  
  40. #define isBetn(x,a,b)        (x>=a && x<=b)
  41. #define isIntSect(a,b,c,d)   ((a>=c && a<=d) || (b>=c && b<=d) || (c>=a && d<=b))
  42.  
  43. typedef long long            ll;
  44. typedef pair<int,int>        pii;
  45. typedef pair<string,int>     psi;
  46. typedef pair<string,string>  pss;
  47. typedef vector<int>          vi;
  48. typedef vector<char>         vc;
  49. typedef vector<string>       vs;
  50. typedef map<int,int>         mii;
  51. typedef map<string,int>      msi;
  52. typedef map<char,int>        mci;
  53.  
  54. //int dx[]={1,-1,0,0},dy[]={0,0,1,-1}; // 4-direction delta
  55. //int dc[]={0,1,0,-1,1,1,-1,-1},dr[]={1,0,-1,0,1,-1,-1,1}; // 8-direction delta
  56. //int dk[]={1,2,2,1,-1,-2,-2,-1},dl[]={2,1,-1,-2,-2,-1,1,2}; // Knight's move
  57.  
  58. typedef struct
  59. {
  60.     int pos;
  61.     int money;
  62. }bank;
  63.  
  64. int m[200005];
  65. bank B[200005];
  66.  
  67. int bsearch(int l,int u,int v)
  68. {
  69.     int mid;
  70.  
  71.     while(l<u)
  72.     {
  73.         mid=(l+u)/2;
  74.  
  75.         if(B[mid].pos<v)
  76.             l=mid+1;
  77.         else
  78.             u=mid;
  79.     }
  80.  
  81.     return u;
  82. }
  83.  
  84. int main()
  85. {
  86.     int n,d,mx;
  87.     int i,a,b;
  88.  
  89.     while(scanf("%d %d",&n,&d)==2)
  90.     {
  91.         REP(i,n)
  92.             scanf("%d %d",&B[i].pos,&B[i].money);
  93.  
  94.         m[n]=0;
  95.         REV(i,n)
  96.             m[i]=max(B[i].money,m[i+1]);
  97.  
  98.         mx=0;
  99.         a=b=-1;
  100.         REP(i,n)
  101.         {
  102.             int ind=bsearch(0,n-1,B[i].pos+d);
  103.  
  104.             if(B[ind].pos>=(B[i].pos+d))
  105.             {
  106.                 if((B[i].money+m[ind])>=mx)
  107.                 {
  108.                     mx=B[i].money+m[ind];
  109.                     a=i+1,b=ind+1;
  110.                 }
  111.             }
  112.         }
  113.  
  114.         printf("%d %d\n",a,b);
  115.     }
  116.  
  117.     return 0;
  118. }
  119.  
  120.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement