Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define forn(i, n) for (int i = 0; i < int(n); i++)
- using namespace std;
- vector < vector <int> > spTAB_min;
- vector < vector <int> > spTAB_max;
- void build_spTAB(vector <int> &arr){
- int n = arr.size();
- int k = (int)log2(n);
- for (int i = 0; i < n; i++){
- spTAB_min[0][i] = arr[i];
- spTAB_max[0][i] = arr[i];
- }
- for (int j = 1; j <= k; j++) {
- for (int i = 0; i + pow(j, 2) <= n; i++) {
- spTAB_min[j][i] = min (spTAB_min[j - 1][i], spTAB_min[j - 1][i + pow(j, 2)]);
- spTAB_max[j][i] = max (spTAB_max[j - 1][i], spTAB_max[j - 1][i + pow(j, 2)]);
- }
- }
- }
- int get_max(int R, int L){
- int k = log2(R - L + 1);
- cout << "MAX FROM " << R << " TO " << L << " = " << min(spTAB_min[k][L], spTAB_min[k][R - pow(k, 2) + 1]) << endl;
- return max(spTAB_max[k][L], spTAB_max[k][R - pow(k, 2) + 1]);
- }
- int get_min(int R, int L){
- int k = log2(R - L + 1);
- cout << "MIN FROM " << R << " TO " << L << " = " << min(spTAB_min[k][L], spTAB_min[k][R - pow(k, 2) + 1]) << endl;
- return min(spTAB_min[k][L], spTAB_min[k][R - pow(k, 2) + 1]);
- }
- int main()
- {
- int n;
- cin >> n;
- vector <int> a(n);
- spTAB_min.resize((int)log2(n)+1, vector <int> (n));
- spTAB_max.resize((int)log2(n)+1, vector <int> (n));
- forn(i, n){
- cin >> a[i];
- }
- build_spTAB(a);
- int ans = 0, r = 0;
- for(int l = 0; l < n; l++){
- while(r < n - 1 && get_max(l, r+1) - get_min(l, r+1) <= 1){
- r++;
- }
- if(get_max(l, r) - get_min(l, r) <= 1){
- ans = max(ans, r - l + 1);
- }
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement