# Untitled

a guest
Nov 13th, 2015
156
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <vector>
2. #include <algorithm>
3. #include <iostream>
4.
5. using namespace std;
6.
7.
8. struct v2
9. {
10.     int a;
11.     int b;
12. };
13.
14. bool sort1(v2 a, v2 b){
15.     if(a.a == b.a)
16.         return a.b < b.b;
17.     return a.a < b.a;
18. }
19. bool sort2(v2 a, v2 b){
20.     if(a.b == b.b)
21.         return a.a < b.a;
22.     return a.b < b.b;
23. }
24.
25. int main()
26. {
27.     int n, x, y=0;
28.     cin >> n;
29.     cin >> x;
30.     cin >> y;
31.     vector<v2> cs; // list of competition starts and end times
32.     for(int i =0;i<n;i++)
33.     {
34.         v2 a;
35.         cin >> a.a;
36.         cin >> a.b;
37.         cs.push_back(a);
38.     }
39.
40.     vector<int> is; //in wormholes
41.     vector<int> es; //out wormholes
42.     for(int i =0;i<x;i++)
43.     {
44.         int ax = 0;
45.         cin >> ax;
46.         is.push_back(ax);
47.     }
48.         for(int i =0;i<y;i++)
49.     {
50.         int ax = 0;
51.         cin >> ax;
52.         es.push_back(ax);
53.     }
54.
55.     //sort in ascending order
56.     sort(is.begin(), is.end());
57.     //sort first by end time, then matched ones are sorted by start time in ascending
58.     sort(cs.begin(), cs.end(), sort2);
59.     sort(es.begin(), es.end());
60.
61.     //compare every single to find the best way giving O(n^3) but because the arrays are
62.     //already sorted we just need to check the first element that fits the condition
63.     //after this the index is saved so that again in next loop we don't check from the beginning
64. int out = 1000000;
65.     int* dp = new int[x]();
66.     int p1 =0, p2=0;
67.     for(int i = 0;i<x;i++)
68.     {
69.         for(int ab = p1; ab<n;ab++)
70.         {
71.             if(cs[ab].a > is[i])
72.             {
73.             //          cout << "B" << is[i] << "\n";
74.
75.                 bool tset = false;
76.                 for(int ac = p2;ac<y;ac++)
77.                 {
78.             //      cout << "C" << es[ac] << "\n";
79.                     if(cs[ab].b <= es[ac])
80.                     {
81.
82.             //cout << "A: " << cs[ab].a << " " << is[i] << " " << es[i] << "\n";
83.                         int time= es[ac] - is[i] + 1;
84.                         if(time < out)
85.                             out = time;
86.                         tset =true;
87.                         break;
88.                     }
89.
90.                     p2 = ac;
91.                 }
92.                 if(tset)
93.                     break;
94.             }
95.
96.             p1 = ab;
97.             //p1++;
98.         }
99.     }
100.     cout << out;
101.
102. }
RAW Paste Data