SRM337 D1M BuildingAdvertise

TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

$N \leq 100000$の要素を持つ配列$R$を作る．$R$中の最大長方形を求める．最大長方形として使われる一番小さい要素を$1$つを全探索する．使う要素$i$を一つ決めると，それが一番小さいという仮定があるので，$[left, i]$と$[i, right]$のminが$R[i]$である必要があり，この条件を満たす端を求める二分探索をすることで答えが求まる．区間$[i, n)$で$min = R[i]$を満たす最も右端$right$と，$(-1, i]$で$min = R[i]$を満たす最も左端$left$が求まったとすると，$i$を一番小さい要素として使用した最大長方形は$R[i] * (right - left)$となる．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,k,n) for(int i=k;i<(int)(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

struct RMQ {
  int n;
  vector<int> dat;
  RMQ(int n_) {
      n = 1;
      while(n < n_) n *= 2;

      dat.resize(n*4);
      rep(i,n*4) dat[i] = INF;
  }
  void update(int k,int a) {
      int i = k+n-1;
      dat[i] = a;

      while(i > 0) {
          i = (i-1) / 2;
          dat[i] = min(dat[i*2+1],dat[i*2+2]);
      }
  }
  //query(a,b,0,0,n) [a,b)
  int _query(int a,int b,int k,int l,int r)
  {
      if(r <= a || b <= l) return INF;

      if(a <= l && r <= b) return dat[k];
      else {
          int vl = _query(a,b,k*2+1,l,(l+r)/2);
          int vr = _query(a,b,k*2+2,(l+r)/2,r);
          return min(vl,vr);
      }
  }

  //[a,b)
  int query(int a,int b) {
      return _query(a,b,0,0,n);
  }
};

class BuildingAdvertise {
  public:
  long long getMaxArea(vector <int> h, int n) {
      vector<ll> R(n);
      int j = 0, m = h.size(), s= 0;

      rep(i, n) {
          R[i] = h[j];
          s = (j+1) % m;
          h[j] = ((h[j] ^ h[s]) + 13) % 835454957;
          j = s;
      }

      RMQ rmq(n);
      rep(i, n) {
          rmq.update(i, R[i]);
      }

      ll ans = 0;
      rep(i, n) {
          // [i, n)
          int l = i, r = n;
          while(r - l > 1) {
              int mid = (r + l) / 2;
              if(rmq.query(i, mid+1) < R[i]) {
                  r = mid;
              } else {
                  l = mid;
              }
          }

          // (-1, i]
          int right = r;
          l = -1, r = i;
          while(r - l > 1) {
              int mid = (r + l) / 2;
              if(rmq.query(mid, i+1) < R[i]) {
                  l = mid;
              } else {
                  r = mid;
              }
          }
          int left = r;

          ans = max(ans, R[i] * (right - left));
      }

      return ans;
  }
};
Feb 6th, 2017
segmenttree, srm, topcoder, 二分探索, 最大長方形