Submission #308891

#	Time	Username	Problem	Language	Result	Execution time	Memory
308891		Matteo_Verz	Fancy Fence (CEOI20_fancyfence)	C++11	100 / 100	51 ms	30200 KiB

fancyfence

/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using pll = pair <ll, ll>;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
template <typename T>
T Max(T a, T b) {
  if(a < b) return b;
  return a;
}
 
template <typename T>
T Min(T a, T b) {
  if(a < b) return a;
  return b;
}
 
template <typename T>
T Abs(T a) {
  if(a < 0) return -a;
  return a;
}
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void SetIO() {
#ifdef BLAT
  freopen("input.in", "r", stdin);
  freopen("output.out", "w", stdout);
#endif // BLAT
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
 
const int MOD = 1e9 + 7;
const int INVMOD = (1e9 + 8) / 2;
const int INF = 1e9;
const int N = 1e5;
const int LOG = 20;
 
pair <int, int> p[5 + N];
ll sp[5 + N];
int n;
 
class RMQ {
  private:
    pair <int, int> r[5 + LOG][5 + N];
    int log[5 + N];
 
  public:
    void Compute_RMQ() {
      log[1] = 0;
      for(int i = 2; i <= n; i++) log[i] = 1 + log[i >> 1];
      for(int i = 1; i <= n; i++) r[0][i] = make_pair(p[i].first, i);
 
      for(int i = 1; i <= log[n]; i++) {
        for(int j = 1; j + (1 << i) - 1 <= n; j++) {
          if(r[i - 1][j].first <= r[i - 1][j + (1 << (i - 1))].first)
            r[i][j] = r[i - 1][j];
          else r[i][j] = r[i - 1][j + (1 << (i - 1))];
 
          //cerr << "i = " << i << "; j = " << j << '\n';
          //cerr << r[i][j].first << " " << r[i][j].second << " ";
        }
        //cerr << '\n';
      }
    }
 
    pair <int, int> Get_Minimum(int from, int to) {
      int lg = log[to - from + 1];
      
      //cerr << "lg = " << lg << '\n';
      //cerr << "r[lg][from].first = " << r[lg][from].first << '\n';
      //cerr << "r[lg][to - (1 << lg) + 1].first = " << r[lg][to - (1 << lg) + 1].first << '\n';
      if(r[lg][from].first <= r[lg][to - (1 << lg) + 1].first)
        return r[lg][from];
      return r[lg][to - (1 << lg) + 1];
    }
};
RMQ rmq;
 
 
ll Solve_From_To(int from, int to, int level = 0) {
  if(from > to) return 0;
  //cerr << from << " " << to << " " << level << '\n';
 
  pair <int, int> minim = rmq.Get_Minimum(from, to);
  //cerr << minim.first << " " << minim.second << '\n';
 
  ll x = (sp[to] - sp[from - 1]) % MOD;
  ll y = (minim.first - level) % MOD;
  // level + 1 + level + 2 + ... + level + h = level * h + h * (h + 1) / 2 = h * ((h + 1) / 2 + level);
 
  x = ((1LL * x * (x + 1)) % MOD) * INVMOD % MOD;
  y = ((1LL * (y + 1) * INVMOD) % MOD + 1LL * level) * y % MOD;
 
  ll rect = (x * y) % MOD;
  //cerr << rect << '\n';
  return (rect + Solve_From_To(from, minim.second - 1, minim.first) % MOD + Solve_From_To(minim.second + 1, to, minim.first) % MOD ) % MOD;
}
 
int main() {
  SetIO();
 
  cin >> n;
 
  for(int i = 1; i <= n; i++) cin >> p[i].first;
  for(int i = 1; i <= n; i++) {
    cin >> p[i].second;
    sp[i] = sp[i - 1] + 1LL * p[i].second;
  }
 
  rmq.Compute_RMQ();
 
  cout << Solve_From_To(1, n);
  return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27