fork download
copy 
  1. /* problem statement text */
  2. /*
  3. CSES - Sliding Window Advertisement
  4.  
  5. Time limit: 1.00 s
  6. Memory limit: 512 MB
  7.  
  8. A fence consists of nnn vertical boards. The width of each board is 1 and their heights may vary.
  9. You want to attach a rectangular advertisement to the fence. Your task is to calculate the maximum area of such an advertisement in each window of kkk vertical boards, from left to right.
  10. Input
  11. The first line contains two integers nnn and kkk: the width of the fence and the size of the window.
  12. After this, there are nnn integers x1,x2,…,xnx_1, x_2, \dots, x_nx1​,x2​,…,xn​: the height of each board.
  13. Output
  14. Print n−k+1n - k + 1n−k+1 integers: the maximum areas of the advertisements.
  15. Constraints
  16.  
  17. 1≤k≤n≤2⋅1051 \le k \le n \le 2 \cdot 10^51≤k≤n≤2⋅105
  18. 1≤xi≤1091 \le x_i \le 10^91≤xi​≤109
  19.  
  20. Example
  21. Input:
  22. 8 3
  23. 4 1 5 3 3 2 4 1
  24.  
  25. Output:
  26. 5 6 9 6 6 4
  27. */
  28. #include <bits/stdc++.h>
  29. using namespace std;
  30. typedef long long ll;
  31. typedef long double ld;
  32.  
  33. void PRE() {
  34.     ios_base::sync_with_stdio(false);
  35.     cin.tie(0);
  36.     cout.tie(0);
  37. #ifndef ONLINE_JUDGE
  38. //    freopen("in.txt", "r", stdin);
  39. //    freopen("out.txt", "w", stdout);
  40. //    freopen("error.txt", "w", stderr);
  41. #endif
  42. }
  43.  
  44. struct LineTree {
  45.     struct TNode {
  46.         ll k, b;
  47.         TNode *l, *r;
  48.  
  49.         TNode() : k(0), b(0), l(nullptr), r(nullptr) {
  50.         }
  51.     };
  52.  
  53.     TNode *root;
  54.     int dl;
  55.     int dr;
  56.  
  57.     bool comp(ll ak, ll ab, ll bk, ll bb, ll x) { return ak * x + ab > bk * x + bb; }
  58.  
  59.     void _modify(TNode *&p, ll k, ll b, int l, int r, int ml, int mr) {
  60.         if (p == nullptr) p = new TNode();
  61.         int mid = (l + r) / 2;
  62.         if (ml <= l && r <= mr) {
  63.             if (l == r) {
  64.                 if (comp(k, b, p->k, p->b, l)) {
  65.                     p->k = k;
  66.                     p->b = b;
  67.                 }
  68.                 return;
  69.             }
  70.             if (comp(k, b, p->k, p->b, mid)) {
  71.                 std::swap(p->k, k);
  72.                 std::swap(p->b, b);
  73.             }
  74.             if (ml <= mid && comp(k, b, p->k, p->b, l)) _modify(p->l, k, b, l, mid, ml, mr);
  75.             if (mid + 1 <= mr && comp(k, b, p->k, p->b, r)) _modify(p->r, k, b, mid + 1, r, ml, mr);
  76.         } else {
  77.             if (mid >= ml) _modify(p->l, k, b, l, mid, ml, mr);
  78.             if (mid < mr) _modify(p->r, k, b, mid + 1, r, ml, mr);
  79.         }
  80.     }
  81.  
  82.     ll _query(TNode *&p, int pos, int l, int r) {
  83.         if (p == nullptr) return 0;
  84.         if (l == r) return p->k * pos + p->b;
  85.         int mid = (l + r) / 2;
  86.         ll ret = p->k * pos + p->b;
  87.         if (pos <= mid) ret = std::max(ret, _query(p->l, pos, l, mid));
  88.         else ret = std::max(ret, _query(p->r, pos, mid + 1, r));
  89.         return ret;
  90.     }
  91.  
  92. public:
  93.     LineTree(int dl, int dr) : dl(dl), dr(dr), root(new TNode()) {
  94.     }
  95.  
  96.     void modify(ll k, ll b, int l, int r) {
  97.         // guard invalid ranges (keeps behavior safe)
  98.         if (l > r) return;
  99.         l = max(l, dl);
  100.         r = min(r, dr);
  101.         if (l > r) return;
  102.         _modify(root, k, b, dl, dr, l, r);
  103.     }
  104.  
  105.     ll query(int pos) { return _query(root, pos, dl, dr); }
  106. };
  107.  
  108. int main() {
  109.     PRE();
  110.  
  111.     int n, k;
  112.     cin >> n >> k;
  113.     vector<ll> a(n);
  114.     for (int i = 0; i < n; ++i) cin >> a[i];
  115.  
  116.     map<ll, vector<int> > app;
  117.     for (int i = 0; i < n; ++i) app[a[i]].push_back(i);
  118.  
  119.     set<int> o;
  120.     for (int i = -1; i <= n; ++i) o.insert(i);
  121.  
  122.     LineTree lt(0, n);
  123.  
  124.     for (auto it = app.rbegin(); it != app.rend(); ++it) {
  125.         ll v = it->first;
  126.         auto &pos_list = it->second;
  127.  
  128.         for (int idx: pos_list) o.erase(idx);
  129.  
  130.         for (int idx: pos_list) {
  131.             auto up = o.upper_bound(idx);
  132.             int left_prev = *prev(up);
  133.             int right_next = *up;
  134.             int l = left_prev + 1;
  135.             int r = right_next - 1;
  136.  
  137.             if (r - k + 1 >= 0) {
  138.                 lt.modify(v, (ll) (k - l) * v, max(0, l - k + 1), min(l, r - k + 1));
  139.             }
  140.             if (r - l + 1 >= k) {
  141.                 lt.modify(0, (ll) k * v, l, r - k + 1);
  142.             }
  143.             lt.modify(-v, (ll) (r + 1) * v, max(l, r - k + 1), r);
  144.             if (r - k + 1 <= l) {
  145.                 lt.modify(0, (ll) (r - l + 1) * v, r - k + 1, l);
  146.             }
  147.         }
  148.     }
  149.  
  150.     for (int i = 0; i + k - 1 < n; ++i) {
  151.         cout << lt.query(i) << (i + k - 1 < n - 1 ? ' ' : '\n');
  152.     }
  153.     if (n - k + 1 <= 0) cout << "\n";
  154. }
  155.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/D11tJ6
language:
C++14 (clang 8.0)
created:
7 hours 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!