v 0. Pasted by slipstak2 as cpp at 2010-11-23 22:52:10 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 6.
  2. // 6A. Закраска прямой [cover]
  3. // ibelyaev: 20Nov2010
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <vector>
  8. #include <algorithm>
  9.  
  10. using namespace std;
  11.  
  12. struct point
  13. {
  14.     int value;
  15.     bool isBegin;
  16.     point(){}
  17.     point(int _value, bool _isBegin)
  18.     {
  19.         value = _value;
  20.         isBegin = _isBegin;
  21.     }
  22. };
  23. int n;
  24. vector<point> mas;
  25. void input()
  26. {
  27.     cin>>n;
  28.     mas.resize(2*n);
  29.     int begin,end;
  30.     for (int i=0;i<2*n;i+=2)
  31.     {
  32.         scanf("%d %d",&begin, &end);
  33.         mas[i]   = point(begin,true);
  34.         mas[i+1] = point(end,false);
  35.     }
  36. }
  37. bool cmpPoint(const point &a, const point &b)
  38. {
  39.     if (a.value != b.value)
  40.         return a.value < b.value;
  41.     if (a.isBegin && !b.isBegin)
  42.         return true;
  43.     return false;
  44. }
  45. void solve()
  46. {
  47.     sort(mas.begin(),mas.end(),cmpPoint);
  48.     int totalLen = 0;
  49.     int segmAmount = 1;
  50.     int prev = mas[0].value;
  51.     for (int i=1;i<mas.size();i++)
  52.     {
  53.         if (segmAmount != 0)
  54.             totalLen += mas[i].value - prev;
  55.         prev = mas[i].value;
  56.         if (mas[i].isBegin)
  57.             segmAmount++;
  58.         else
  59.             segmAmount--;
  60.     }
  61.     cout<<totalLen;
  62. }
  63. int main()
  64. {
  65.     freopen("input.txt","r",stdin);
  66.     freopen("output.txt","w",stdout);
  67.    
  68.     input();
  69.     solve();
  70.     return 0;
  71. }


Editing is locked.