mrlolthe1st

Untitled

Sep 21st, 2021
639
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <cstring>
  4. #include <string>
  5. #include <vector>
  6. #include <map>
  7. #include <chrono>
  8. #include <unordered_map>
  9. #include <list>
  10. #include <numeric>
  11. #include <set>
  12. #include <algorithm>
  13. #include <unordered_set>
  14. #include <assert.h>
  15. #include <fstream>
  16. #include <sstream>
  17. using namespace std;
  18. #define vi vector<int>
  19. #define vec vector
  20. #define F first
  21. #define S second
  22.  
  23. vi merge_upd(const vi& a, const vi& b) {
  24.     int l = 0, r = 0;
  25.     vi res;
  26.     while (l < a.size() && r < b.size()) {
  27.         if (a[l] < b[r]) {
  28.             res.push_back(a[l++]);
  29.         }
  30.         else {
  31.             res.push_back(b[r++]);
  32.         }
  33.     }
  34.     while (l < a.size()) res.push_back(a[l++]);
  35.     while (r < b.size()) res.push_back(b[r++]);
  36.     return res;
  37. }
  38.  
  39. vec<vi> t;
  40. void build(vi a) {
  41.     while ((a.size() & (a.size() - 1))) a.push_back(0);
  42.     t.resize(a.size() << 1);
  43.     for (int i = 0; i < a.size(); ++i) {
  44.         t[i + a.size()] = { a[i] };
  45.     }
  46.     for (int i = a.size() - 1; i > 0; --i) {
  47.         t[i] = merge_upd(t[i * 2], t[i * 2 + 1]);
  48.     }
  49. }
  50.  
  51. int query(int v, int vl, int vr, int l, int r) {
  52.     if (vl > vr || l > vr || r < vl) return {};
  53.     if (l <= vl && vr <= r) {
  54.         int i = upper_bound(t[v].begin(), t[v].end(), r) - t[v].begin();
  55.         return t[v].size() - i;
  56.     }
  57.     int m = (vl + vr) >> 1;
  58.     return query(v * 2, vl, m, l, r) + query(v * 2 + 1, m + 1, vr, l, r);
  59. }
  60.  
  61. vec<pair<int, int>> T;
  62. void build2(vec<pair<int, int>> a) {
  63.     while ((a.size() & (a.size() - 1))) a.push_back({ -1e9, a.size() });
  64.     T.resize(a.size() << 1);
  65.     for (int i = 0; i < a.size(); ++i) {
  66.         T[i + a.size()] = { a[i] };
  67.     }
  68.     for (int i = a.size() - 1; i > 0; --i) {
  69.         T[i] = max(T[i * 2], T[i * 2 + 1]);
  70.     }
  71. }
  72.  
  73. pair<int, int> query2(int v, int vl, int vr, int l, int r) {
  74.     if (vl > vr || l > vr || r < vl) return {};
  75.     if (l <= vl && vr <= r) {
  76.         return T[v];
  77.     }
  78.     int m = (vl + vr) >> 1;
  79.     return max(query2(v * 2, vl, m, l, r), query2(v * 2 + 1, m + 1, vr, l, r));
  80. }
  81.  
  82.  
  83. pair<int, int> go(vi& a, int L, int R, int A, int B) {
  84.     vi b(a.size());
  85.     unordered_map<int, int> pos;
  86.     vec<pair<int, int>> pref(a.size());
  87.     int s = 0;
  88.     for (int i = a.size() - 1; i > -1; --i) {
  89.         if (pos.count(a[i])) {
  90.             b[i] = pos[a[i]];
  91.         }
  92.         else b[i] = a.size();
  93.         pos[a[i]] = i;
  94.     }
  95.     for (int i = 0; i < a.size(); ++i) {
  96.  
  97.         s += a[i];
  98.         pref[i] = { s, i };
  99.     }
  100.     build(b);
  101.     build2(pref);
  102.     int mx = -1e9;
  103.     int al = -1, ar = -1;
  104.     for (int i = 0; i < a.size() - R + 1; ++i) {
  105.         // Давайте найдем такое самое правое l, что кол-во различных на
  106.         // отрезке от i до l <= B
  107.         int l = i + L, r = i + R;
  108.         while (l < r - 1) {
  109.             int m = (l + r) >> 1;
  110.             if (query(1, 0, (t.size() >> 1) - 1, i, m) > B) r = m;
  111.             else l = m;
  112.         }
  113.         int r1 = query(1, 0, (t.size() >> 1) - 1, i, l);
  114.         // Если кол-во различных на минимальном отрезке от i до i+L < A || > B
  115.         if (r1 > B || r1 < A) continue;
  116.  
  117.         int xl = l;
  118.         // Давайте найдем такое самое правое l, что кол-во различных на
  119.         // отрезке от i до l <= A
  120.         l = i + L, r = i + R;
  121.         while (l < r - 1) {
  122.             int m = (l + r) >> 1;
  123.             if (query(1, 0, (t.size() >> 1) - 1, i, m) > A) r = m;
  124.             else l = m;
  125.         }
  126.  
  127.         // Ну если не нашли - ну и ладно
  128.         if (query(1, 0, (t.size() >> 1) - 1, i, l) < A) continue;
  129.         // Найдем максимум на префиксе от l до xl -> это и будет ответом
  130.         auto x = query2(1, 0, (t.size() >> 1) - 1, l, xl);
  131.         int sum = x.first - (i ? pref[i - 1].first : 0);
  132.         if (sum > mx) {
  133.             al = i; ar = x.second;
  134.             mx = sum;
  135.         }
  136.  
  137.     }
  138.     return { al, ar };
  139. }
  140.  
  141. pair<int, int> go2(vi& a, int L, int R, int A, int B) {
  142.     int mx = -1e9, al = -1, ar = -1;
  143.     for (int i = 0; i < a.size() - R + 1; ++i) {
  144.         unordered_set<int> el;
  145.         int sum = 0;
  146.         for (int j = 0; j < L - 1; ++j) el.insert(a[j + i]), sum += a[j + i];
  147.         for (int j = L - 1; j < R; ++j) {
  148.             sum += a[j + i];
  149.             el.insert(a[j + i]);
  150.             if (A <= el.size() && el.size() <= B) {
  151.                 if (sum >= mx) {
  152.                     mx = sum;
  153.                     al = i;
  154.                     ar = i + j;
  155.                 }
  156.             }
  157.  
  158.         }
  159.     }
  160.     return { al, ar };
  161. }
  162.  
  163. signed main() {
  164. #ifndef _MSVC_LANG
  165.     freopen("painter.in", "r", stdin);
  166.     freopen("painter.out", "w", stdout);
  167. #endif
  168.     int n, l, r, a, b;
  169.     n = 100;
  170.     l = 2; r = 20;
  171.     a = 1; b = 10;
  172.     vi aa(n);
  173.     int t = 1e5;
  174.     while (t--) {
  175.         for (auto& e : aa)e = rand() % 250;
  176.         if (!(t % 100)) cout << t << "\n";
  177.         auto r1 = go(aa, l, r, a, b);
  178.         auto r2 = go2(aa, l, r, a, b);
  179.         set<int> xa;
  180.         int s = 0;
  181.         for (int j = r1.first; j <= r1.second; ++j)xa.insert(aa[j]), s += aa[j];
  182.         set<int> xb;
  183.         int ss = 0;
  184.         for (int j = r2.first; j <= r2.second; ++j)xb.insert(aa[j]), ss += aa[j];
  185.  
  186.         if (!(ss == s && a <= xa.size() && xa.size() <= b && a <= xb.size() && xb.size() <= b)) {
  187.             cout << "!";
  188.             assert(false);
  189.             go2(aa, l, r, a, b);
  190.         }
  191.     }
  192.  
  193. }
RAW Paste Data