Advertisement
iletavcioski

Untitled

Mar 20th, 2017
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.47 KB | None | 0 0
  1. /**
  2.  * Solution to IOI 2009 problem "salesman"
  3.  *
  4.  * We use a C++ set to store the list of currently "active" fairs,
  5.  * where an active fair is one that has a better profit than by
  6.  * visiting the fair than reaching the same location from some
  7.  * other fair. We then process the fairs in order of the time at
  8.  * which they occur, using our active set to find the best fair
  9.  * to come from in order to visit each new successive fair, and
  10.  * updating the active set with the new fair afterwards.
  11.  *
  12.  * For fairs on the same day, we note that the most efficient
  13.  * way of visiting these is to pick one as a starting point and
  14.  * then visit fairs in a single direction. We test both the
  15.  * upstream and downstream directions, and for each fair decide
  16.  * whether it is better to go directly to this fair or to come
  17.  * from the previous fair opposite to the direction in which
  18.  * we are travelling.
  19.  *
  20.  */
  21.  
  22. #include <iostream>
  23. #include <cassert>
  24. #include <set>
  25. #include <algorithm>
  26. #include <cmath>
  27. #include <cstdio>
  28. #include <vector>
  29.  
  30. using namespace std;
  31.  
  32. #define MAX_N 500000
  33. #define MAX_D_U 10
  34. #define MAX_S 500001
  35. #define MAX_T 500000
  36. #define MAX_L 500001
  37. #define MAX_M 4000
  38.  
  39. int n, d, u, s;
  40.  
  41. // Class for storing all the things we want to associate with a fair
  42. typedef struct fair
  43. {
  44.     int t, l, m;
  45.     int best;
  46.  
  47.     // Used for traversing upstream and downstream when fairs occur
  48.     // on the same day.
  49.     int baseBest;
  50.     int curBest;
  51.  
  52.     // Order fairs first according to time, and secondly according
  53.     // to their location (which makes the upstream and downstream
  54.     // traversals much easier).
  55.     bool operator <(const fair &f) const
  56.     {
  57.         if (t < f.t)
  58.             return true;
  59.         else if (t == f.t && l < f.l)
  60.             return true;
  61.         else
  62.             return false;
  63.     }
  64. } fair;
  65.  
  66. // For our set, we want to order fairs by location only, so have
  67. // a special comparator for this.
  68. struct location_less
  69. {
  70.     bool operator ()(const fair &x, const fair &y)
  71.     {
  72.         return x.l < y.l;
  73.     }
  74. };
  75.  
  76. vector<fair> fairs;
  77. set<fair, location_less> activeFairs;
  78.  
  79. /**
  80.  * Computes the cost of travelling between two points on the river.
  81.  */
  82. double travelCost(double from, double to)
  83. {
  84.     if (from < to)
  85.         return (to - from) * d;
  86.     else
  87.         return (from - to) * u;
  88. }
  89.  
  90. /**
  91.  * Queries for the best profit that we can expect to earn when
  92.  * visiting fair i directly from some fair that occurred on a
  93.  * previous day.
  94.  *
  95.  * We find the active fairs that occur to the left and right of
  96.  * this one along the river -- it is fairly easy to show that our
  97.  * optimal predecessor must be one of these fairs. Then we pick
  98.  * the one which gives us a greater profit.
  99.  */
  100. int query(int i)
  101. {
  102.     set<fair, location_less>::iterator low = activeFairs.lower_bound(fairs[i]);
  103.     set<fair, location_less>::iterator high = low;
  104.  
  105.     if (low != activeFairs.begin())
  106.         low--;
  107.     if (high == activeFairs.end())
  108.         high--;
  109.  
  110.     return max(low->best - travelCost(low->l, fairs[i].l),
  111.                high->best - travelCost(high->l, fairs[i].l)) + fairs[i].m;
  112. }
  113.  
  114. /**
  115.  * Updates our active fairs set with the given fair. Care must be
  116.  * taken to ensure that this fair is actually active (if all fairs
  117.  * are on distinct days then it will be, but if there are several on
  118.  * the same day then there may be a better path to this location on
  119.  * the river via some other fair).
  120.  */
  121. void update(int i)
  122. {
  123.     // Insert by default, we will remove it later if we need to.
  124.     activeFairs.insert(fairs[i]);
  125.  
  126.     set<fair, location_less>::iterator thisFair = activeFairs.lower_bound(fairs[i]);
  127.     set<fair, location_less>::iterator cur = thisFair;
  128.  
  129.     // Check upstream fairs
  130.     while (cur != activeFairs.begin())
  131.     {
  132.         cur--;
  133.  
  134.         // Check if the fair we have just added is covered by the
  135.         // previous fair in the set.
  136.         if (cur->best - travelCost(cur->l, thisFair->l) >= thisFair->best)
  137.         {
  138.             // Yes, so remove and return
  139.             activeFairs.erase(thisFair);
  140.             return;
  141.         }
  142.  
  143.         // Check if the fair we have just added covers the previous
  144.         // fair in the set.
  145.         if (thisFair->best - travelCost(thisFair->l, cur->l) < cur->best)
  146.             // No, so stop removing non-active fairs
  147.             break;
  148.  
  149.         // Remove the fair that is covered by our recently added one,
  150.         // and which is thus no longer active.
  151.         activeFairs.erase(cur);
  152.         cur = thisFair;
  153.     }
  154.  
  155.     // Check downstream fairs
  156.     cur = thisFair;
  157.     cur++;
  158.     while (cur != activeFairs.end())
  159.     {
  160.         // Check if the fair we have just added is covered by the
  161.         // next fair in the set.
  162.         if (cur->best - travelCost(cur->l, thisFair->l) >= thisFair->best)
  163.         {
  164.             // Yes, so remove and return
  165.             activeFairs.erase(thisFair);
  166.             return;
  167.         }
  168.  
  169.         // Check if the fair we have just added covers the next
  170.         // fair in the set.
  171.         if (thisFair->best - travelCost(thisFair->l, cur->l) < cur->best)
  172.             break;
  173.  
  174.         // Remove the fair that is covered by our recently added one,
  175.         // and which is thus no longer active.
  176.         activeFairs.erase(cur);
  177.         cur = thisFair;
  178.         cur++;
  179.     }
  180. }
  181.  
  182. int main()
  183. {
  184.     scanf("%d %d %d %d", &n, &u, &d, &s);
  185.  
  186.     assert(1 <= n && n <= MAX_N);
  187.     assert(1 <= d && d <= MAX_D_U);
  188.     assert(1 <= u && u <= MAX_D_U);
  189.     assert(1 <= s && s <= MAX_S);
  190.  
  191.     fairs.resize(n + 2);
  192.     int maxT = 0;
  193.     for (int i = 1; i <= n; i++)
  194.     {
  195.         scanf("%d %d %d", &fairs[i].t, &fairs[i].l, &fairs[i].m);
  196.  
  197.         assert(1 <= fairs[i].t && fairs[i].t <= MAX_T);
  198.         assert(1 <= fairs[i].l && fairs[i].l <= MAX_L);
  199.         assert(1 <= fairs[i].m && fairs[i].m <= MAX_M);
  200.  
  201.         maxT = max(maxT, fairs[i].t);
  202.     }
  203.  
  204.     // Create a dummy fairs for the salesman's home at the beginning,
  205.     // and also one at the end
  206.     fairs[0].l = s;
  207.     fairs[0].best = 0;
  208.     fairs[0].t = -1;
  209.     fairs[n + 1].l = s;
  210.     fairs[n + 1].m = 0;
  211.     fairs[n + 1].t = maxT + 1;
  212.  
  213.     sort(fairs.begin(), fairs.end());
  214.  
  215.     // At the beginning, only fair 0 (the salesman's home) is active
  216.     activeFairs.insert(fairs[0]);
  217.  
  218.     for (int i = 1; i <= n; i++)
  219.     {
  220.         // Check to see if we have multiple fairs on the same day
  221.         if (i == n || fairs[i].t != fairs[i + 1].t)
  222.         {
  223.             // No, so just do the simple approach of querying for
  224.             // the best fair to come from in order to reach this
  225.             // one, and update our data structure.
  226.  
  227.             fairs[i].best = query(i);
  228.  
  229.             update(i);
  230.         }
  231.         else
  232.         {
  233.             // Yes, there are multiple fairs happening on this day. We need
  234.             // to choose the best way of picking which of these fairs to
  235.             // visit.
  236.             int first = i;
  237.             while (i <= n && fairs[i].t == fairs[first].t)
  238.                 i++;
  239.             i--;
  240.             int last = i;
  241.  
  242.             // First, find the cheapest way of reaching each fair on this
  243.             // day if we visit no other fairs on the same day.
  244.             for (int j = first; j <= last; j++)
  245.             {
  246.                 fairs[j].baseBest = query(j);
  247.                 fairs[j].best = fairs[j].baseBest;
  248.             }
  249.  
  250.             // Now visit each of the fairs in both an upstream and
  251.             // downstream direction, in each case seeing if it was
  252.             // better to come via the previous fair.
  253.             fairs[first].curBest = fairs[first].baseBest;
  254.             for (int j = first + 1; j <= last; j++)
  255.             {
  256.                 // See if it is better to come from the previous
  257.                 // fair.
  258.                 int profit = fairs[j - 1].curBest - travelCost(fairs[j - 1].l, fairs[j].l) + fairs[j].m;
  259.                 if (profit > fairs[j].baseBest)
  260.                     fairs[j].curBest = profit;
  261.                 else
  262.                     fairs[j].curBest = fairs[j].baseBest;
  263.  
  264.                 if (fairs[j].curBest > fairs[j].best)
  265.                     fairs[j].best = fairs[j].curBest;
  266.             }
  267.  
  268.             // And upstream. Don't forget to start off with the base
  269.             // value of visiting this fair directly (otherwise we will
  270.             // use values fro the downstream pass, which will be
  271.             // confusing).
  272.             fairs[last].curBest = fairs[last].baseBest;
  273.             for (int j = last - 1; j >= first; j--)
  274.             {
  275.                 // See if it is better to come from the previous
  276.                 // fair.
  277.                 int profit = fairs[j + 1].curBest - travelCost(fairs[j + 1].l, fairs[j].l) + fairs[j].m;
  278.                 if (profit > fairs[j].baseBest)
  279.                     fairs[j].curBest = profit;
  280.                 else
  281.                     fairs[j].curBest = fairs[j].baseBest;
  282.  
  283.                 if (fairs[j].curBest > fairs[j].best)
  284.                     fairs[j].best = fairs[j].curBest;
  285.             }
  286.  
  287.             // Update our query structure for all of these fairs, and
  288.             // see if there is a better way home from any of them.
  289.             for (int j = first; j <= last; j++)
  290.                 update(j);
  291.         }
  292.     }
  293.  
  294.     int best = query(n + 1);
  295.  
  296.     // Check that our profit is positive; if not then output 0
  297.     // (indicating that the salesman simply stays at home for the
  298.     // year).
  299.     cout << (best < 0 ? 0 : best) << endl;
  300.  
  301.     return 0;
  302. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement