fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define mod 1000000007
  4. typedef long long int lli;
  5.  
  6. class node
  7. {
  8. public:
  9.     lli xi,pi,low,high;
  10. };
  11. node a[100005];
  12.  
  13. bool Comp(const node& x, const node& y)
  14. {
  15.     return x.low<y.low;
  16. }
  17.  
  18. int main()
  19. {
  20.     std::ios::sync_with_stdio(0);
  21.     int t,n,i,j;
  22.     lli s,e;
  23.     //cin>>t;
  24.  
  25.         cin>>n>>s>>e;
  26.         for(i=0;i<n;i++)
  27.         {
  28.             cin>>a[i].xi>>a[i].pi;
  29.             a[i].low=a[i].xi-a[i].pi;
  30.             a[i].high=a[i].xi+a[i].pi;
  31.         }
  32.         lli cnt=0;
  33.         sort(a,a+n,Comp);
  34.         lli prev=-1;
  35.         for(i=0;i<n;i++)
  36.         {
  37.             if(i==0 && e<=a[i].low)
  38.             {
  39.                 cnt+=s-e;
  40.                 break;
  41.             }
  42.             else if(i==0 && e<=a[i].high)
  43.             {
  44.                 cnt+=max(a[i].low-s,(lli)0);
  45.                 break;
  46.             }
  47.             else if(i==0)
  48.             {
  49.                 cnt+=max(a[i].low-s,(lli)0);
  50.                 prev=max(a[i].high,prev);
  51.             }
  52.             if(s>=a[i].high) 
  53.             {
  54.                 prev=max(a[i].high,prev);
  55.                 continue;
  56.             }
  57.             if(e<=a[i].low) //terminate
  58.             {
  59.                 if(s>=prev) cnt+=e-s;
  60.                 else cnt+=e-prev;
  61.                 break;
  62.             }
  63.             else if(e<=a[i].high)  //terminate
  64.             {
  65.                 if(s>=prev) cnt+=max(a[i].low-s,(lli)0);
  66.                 else cnt+=max((lli)a[i].low-(lli)prev,(lli)0);
  67.                 break;
  68.             }
  69.             else
  70.             {
  71.                 cnt+=max((lli)a[i].low-max((lli)s,(lli)prev),(lli)0);
  72.                 prev=max(a[i].high,prev);
  73.             }
  74.             //cout<<cnt<<" ";
  75.         }
  76.         cout<<cnt<<endl;
  77.  
  78. }
Runtime error #stdin #stdout 0s 6404KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VUrXdJ
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!