Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int offset = (1<<17);
- const int inf = 1e9 + 100;
- int n;
- vector <int> poz;
- vector <int> rad;
- vector <pair <int, int> > granice;
- vector <pair <int, int> > grkomp;
- vector <vector <int> > graf;
- vector <vector <int> > obrnuti;
- vector <vector <int> > novi;
- vector <int> vi;
- vector <int> stek;
- bool bio [offset * 2];
- int komp [offset * 2];
- int brojac = 0;
- void povezi(int cvor, int a, int b, int l, int r, int koga)
- {
- if (l > b || r < a) return;
- if (l >= a && r <= b)
- {
- //cout << "povezujem " << koga << " " << cvor << endl;
- graf [koga].push_back(cvor);
- obrnuti [cvor].push_back(koga);
- return;
- }
- int mid = (l + r) / 2;
- povezi(cvor * 2, a, b, l, mid, koga);
- povezi(cvor * 2 + 1, a, b, mid + 1, r, koga);
- return;
- }
- void dfs(int cvor)
- {
- bio [cvor] = 1;
- for (int i = 0; i < (int) graf [cvor].size(); i++)
- {
- if (!bio [graf [cvor] [i]])
- {
- dfs(graf [cvor] [i]);
- }
- }
- stek.push_back(cvor);
- return;
- }
- void dfs2(int cvor)
- {
- bio [cvor] = 1;
- komp [cvor] = brojac;
- for (int i = 0; i < (int) obrnuti [cvor].size(); i++)
- {
- if (!bio [obrnuti [cvor] [i]])
- {
- dfs2(obrnuti [cvor] [i]);
- }
- }
- return;
- }
- void dfs3(int cvor)
- {
- bio[cvor] = 1;
- for (int j = 0; j < (int) novi [cvor].size(); j++)
- {
- if (bio [novi [cvor] [j]])
- {
- grkomp[cvor].first = min(grkomp[cvor].first, grkomp [novi [cvor] [j]].first);
- grkomp[cvor].second = max(grkomp[cvor].second, grkomp [novi [cvor] [j]].second);
- }
- else
- {
- dfs3(novi [cvor] [j]);
- grkomp[cvor].first = min(grkomp[cvor].first, grkomp [novi [cvor] [j]].first);
- grkomp[cvor].second = max(grkomp[cvor].second, grkomp [novi [cvor] [j]].second);
- }
- }
- return;
- }
- int main()
- {
- graf.insert(graf.begin(), 2 * offset, vi);
- obrnuti.insert(obrnuti.begin(), 2 * offset, vi);
- for (int i = 1; i < offset; i++)
- {
- graf[i].push_back(i * 2);
- graf[i].push_back(i * 2 + 1);
- obrnuti[i * 2].push_back(i);
- obrnuti[i * 2 + 1].push_back(i);
- }
- int x, mini, maxi;
- scanf("%d", &n);
- for (int i = 0; i < n; i++)
- {
- scanf("%d", &x);
- poz.push_back(x);
- }
- for (int i = 0; i < n; i++)
- {
- scanf("%d", &x);
- mini = lower_bound(poz.begin(), poz.end(), poz [i] - x) - poz.begin();
- maxi = (--upper_bound(poz.begin(), poz.end(), poz [i] + x)) - poz.begin();
- granice.push_back(make_pair(mini, maxi));
- povezi(1, mini, maxi, 0, offset - 1, offset + i);
- }
- /*for (int i = 1; i < offset * 2; i++)
- {
- cout << i << " : ";
- for (int j = 0; j < (int) graf [i].size(); j++)
- {
- cout << graf [i] [j] << " ";
- }
- cout << endl;
- }*/
- dfs(1);
- memset(bio, 0, sizeof bio);
- while(stek.size())
- {
- if (bio [stek.back()]) {stek.pop_back(); continue;}
- dfs2(stek.back());
- brojac++;
- stek.pop_back();
- }
- /*cout << "brojac : " << brojac << endl;
- for (int i = 0; i < n; i++)
- {
- cout << "komponenta " << i << " " << komp [offset + i] << endl;
- }*/
- novi.insert(novi.begin(), brojac, vi);
- for (int i = 1; i < offset * 2; i++)
- {
- for (int j = 0; j < (int) graf [i].size(); j++)
- {
- if (komp [i] != komp [graf [i] [j]])
- {
- novi[komp [i]].push_back(komp[graf [i] [j]]);
- }
- }
- }
- /*for (int i = 1; i < offset * 2; i++)
- {
- cout << i << " : ";
- for (int j = 0; j < (int) graf [i].size(); j++)
- {
- cout << graf [i] [j] << " ";
- }
- cout << endl;
- }*/
- for (int i = 0; i < brojac; i++)
- {
- grkomp.push_back(make_pair(inf, -inf));
- }
- for (int i = offset; i < offset + n; i++)
- {
- grkomp[komp[i]].first = min(grkomp[komp[i]].first, granice [i - offset].first);
- grkomp[komp[i]].second = max(grkomp[komp[i]].second, granice [i - offset].second);
- }
- memset(bio, 0, sizeof bio);
- for (int i = 0; i < brojac; i++)
- {
- if (!bio[i]) dfs3(i);
- }
- int rj = -1, koji = -1, trrj;
- for (int i = 0; i < n; i++)
- {
- trrj = grkomp[komp[offset + i]].second - grkomp[komp[offset + i]].first + 1;
- if (trrj > rj)
- {
- rj = trrj;
- koji = i;
- }
- }
- printf("%d %d\n", rj, koji + 1);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement