Advertisement
Guest User

Untitled

a guest
Nov 12th, 2018
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.67 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int offset = (1<<17);
  5. const int inf = 1e9 + 100;
  6.  
  7. int n;
  8.  
  9. vector <int> poz;
  10. vector <int> rad;
  11. vector <pair <int, int> > granice;
  12. vector <pair <int, int> > grkomp;
  13.  
  14. vector <vector <int> > graf;
  15. vector <vector <int> > obrnuti;
  16. vector <vector <int> > novi;
  17. vector <int> vi;
  18.  
  19. vector <int> stek;
  20.  
  21. bool bio [offset * 2];
  22.  
  23. int komp [offset * 2];
  24. int brojac = 0;
  25.  
  26. void povezi(int cvor, int a, int b, int l, int r, int koga)
  27. {
  28.     if (l > b || r < a) return;
  29.     if (l >= a && r <= b)
  30.     {
  31.         //cout << "povezujem " << koga << " " << cvor << endl;
  32.         graf [koga].push_back(cvor);
  33.         obrnuti [cvor].push_back(koga);
  34.         return;
  35.     }
  36.     int mid = (l + r) / 2;
  37.     povezi(cvor * 2, a, b, l, mid, koga);
  38.     povezi(cvor * 2 + 1, a, b, mid + 1, r, koga);
  39.     return;
  40. }
  41.  
  42. void dfs(int cvor)
  43. {
  44.     bio [cvor] = 1;
  45.     for (int i = 0; i < (int) graf [cvor].size(); i++)
  46.     {
  47.         if (!bio [graf [cvor] [i]])
  48.         {
  49.             dfs(graf [cvor] [i]);
  50.         }
  51.     }
  52.     stek.push_back(cvor);
  53.     return;
  54. }
  55.  
  56. void dfs2(int cvor)
  57. {
  58.     bio [cvor] = 1;
  59.     komp [cvor] = brojac;
  60.     for (int i = 0; i < (int) obrnuti [cvor].size(); i++)
  61.     {
  62.         if (!bio [obrnuti [cvor] [i]])
  63.         {
  64.             dfs2(obrnuti [cvor] [i]);
  65.         }
  66.     }
  67.     return;
  68. }
  69.  
  70. void dfs3(int cvor)
  71. {
  72.     bio[cvor] = 1;
  73.     for (int j = 0; j < (int) novi [cvor].size(); j++)
  74.     {
  75.         if (bio [novi [cvor] [j]])
  76.         {
  77.             grkomp[cvor].first = min(grkomp[cvor].first, grkomp [novi [cvor] [j]].first);
  78.             grkomp[cvor].second = max(grkomp[cvor].second, grkomp [novi [cvor] [j]].second);
  79.         }
  80.         else
  81.         {
  82.             dfs3(novi [cvor] [j]);
  83.             grkomp[cvor].first = min(grkomp[cvor].first, grkomp [novi [cvor] [j]].first);
  84.             grkomp[cvor].second = max(grkomp[cvor].second, grkomp [novi [cvor] [j]].second);
  85.         }
  86.     }
  87.     return;
  88. }
  89.  
  90. int main()
  91. {
  92.     graf.insert(graf.begin(), 2 * offset, vi);
  93.     obrnuti.insert(obrnuti.begin(), 2 * offset, vi);
  94.     for (int i = 1; i < offset; i++)
  95.     {
  96.         graf[i].push_back(i * 2);
  97.         graf[i].push_back(i * 2 + 1);
  98.         obrnuti[i * 2].push_back(i);
  99.         obrnuti[i * 2 + 1].push_back(i);
  100.     }
  101.     int x, mini, maxi;
  102.     scanf("%d", &n);
  103.     for (int i = 0; i < n; i++)
  104.     {
  105.         scanf("%d", &x);
  106.         poz.push_back(x);
  107.     }
  108.     for (int i = 0; i < n; i++)
  109.     {
  110.         scanf("%d", &x);
  111.         mini = lower_bound(poz.begin(), poz.end(), poz [i] - x) - poz.begin();
  112.         maxi = (--upper_bound(poz.begin(), poz.end(), poz [i] + x)) - poz.begin();
  113.         granice.push_back(make_pair(mini, maxi));
  114.         povezi(1, mini, maxi, 0, offset - 1, offset + i);
  115.     }
  116.     /*for (int i = 1; i < offset * 2; i++)
  117.     {
  118.         cout << i << " : ";
  119.         for (int j = 0; j < (int) graf [i].size(); j++)
  120.         {
  121.             cout << graf [i] [j] << " ";
  122.         }
  123.         cout << endl;
  124.     }*/
  125.     dfs(1);
  126.     memset(bio, 0, sizeof bio);
  127.     while(stek.size())
  128.     {
  129.         if (bio [stek.back()]) {stek.pop_back(); continue;}
  130.         dfs2(stek.back());
  131.         brojac++;
  132.         stek.pop_back();
  133.     }
  134.     /*cout << "brojac : " << brojac << endl;
  135.     for (int i = 0; i < n; i++)
  136.     {
  137.         cout << "komponenta " << i << " " << komp [offset + i] << endl;
  138.     }*/
  139.     novi.insert(novi.begin(), brojac, vi);
  140.     for (int i = 1; i < offset * 2; i++)
  141.     {
  142.         for (int j = 0; j < (int) graf [i].size(); j++)
  143.         {
  144.             if (komp [i] != komp [graf [i] [j]])
  145.             {
  146.                 novi[komp [i]].push_back(komp[graf [i] [j]]);
  147.             }
  148.         }
  149.     }
  150.     /*for (int i = 1; i < offset * 2; i++)
  151.     {
  152.         cout << i << " : ";
  153.         for (int j = 0; j < (int) graf [i].size(); j++)
  154.         {
  155.             cout << graf [i] [j] << " ";
  156.         }
  157.         cout << endl;
  158.     }*/
  159.     for (int i = 0; i < brojac; i++)
  160.     {
  161.         grkomp.push_back(make_pair(inf, -inf));
  162.     }
  163.     for (int i = offset; i < offset + n; i++)
  164.     {
  165.         grkomp[komp[i]].first = min(grkomp[komp[i]].first, granice [i - offset].first);
  166.         grkomp[komp[i]].second = max(grkomp[komp[i]].second, granice [i - offset].second);
  167.     }
  168.     memset(bio, 0, sizeof bio);
  169.     for (int i = 0; i < brojac; i++)
  170.     {
  171.         if (!bio[i]) dfs3(i);
  172.     }
  173.     int rj = -1, koji = -1, trrj;
  174.     for (int i = 0; i < n; i++)
  175.     {
  176.         trrj = grkomp[komp[offset + i]].second - grkomp[komp[offset + i]].first + 1;
  177.         if (trrj > rj)
  178.         {
  179.             rj = trrj;
  180.             koji = i;
  181.         }
  182.     }
  183.     printf("%d %d\n", rj, koji + 1);
  184.     return 0;
  185. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement