Advertisement
juaniisuar

Untitled

Jun 27th, 2015
470
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.61 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <stack>
  6. #define forn(i,n) for((i)=0;(i)<(n);(i)++)
  7.  
  8. using namespace std;
  9.  
  10. long long N,L,C;
  11.  
  12. struct elem{
  13. char type;
  14. long long index,coor,batt;
  15. };
  16.  
  17. struct kappa{
  18. long long index, maxd;
  19. };
  20.  
  21. bool operator < (const elem a, const elem b){
  22. return a.coor<b.coor;
  23. }
  24.  
  25. vector <elem> EL;
  26. stack <kappa> ST;
  27.  
  28. int main()
  29. {
  30. long long i,j,k,l,explored=0;
  31. freopen("B.in","r",stdin);
  32. scanf("%lld %lld %lld", &N, &L, &C);
  33. elem aux;
  34. kappa keepo;
  35. long long cave[C+5];
  36.  
  37. forn(i,N){
  38. scanf("%lld %lld", &j, &k);
  39. aux.type='R'; aux.index=i+1; aux.coor=j; aux.batt=k;
  40. EL.push_back(aux);
  41. }
  42.  
  43. forn(i,C){
  44. scanf("%lld", &j);
  45. aux.type='C'; aux.index=i; aux.coor=j; aux.batt=0;
  46. EL.push_back(aux);
  47. }
  48.  
  49. sort(EL.begin(),EL.end());
  50.  
  51. forn(i,EL.size()){
  52. if(EL[i].type=='R'){
  53. keepo.index=EL[i].index;
  54. keepo.maxd=EL[i].coor+EL[i].batt;
  55. ST.push(keepo);
  56. }
  57.  
  58. else{
  59. while(!ST.empty()){
  60. keepo=ST.top();
  61. if(keepo.maxd>=EL[i].coor){
  62. cave[ EL[i].index ] = keepo.index;
  63. explored++;
  64. break;
  65. }
  66. else
  67. ST.pop();
  68. }
  69. if(ST.empty())
  70. cave[ EL[i].index ]=-1;
  71. }
  72. }
  73.  
  74. printf("%lld\n",explored);
  75. forn(i,C)
  76. printf("%lld\n",cave[i]);
  77. return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement