• API
• FAQ
• Tools
• Trends
• Archive
SHARE
TWEET

# Untitled

iletavcioski Mar 20th, 2017 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }
RAW Paste Data
Top