Submission #746872

#	Time	Username	Problem	Language	Result	Execution time	Memory
746872		vjudge1	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	183 ms	16340 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

ll solve_rect(ll h, ll w) {
  h %= mod;
  w %= mod;
  ll hc = (h * (h + 1) / 2) % mod;
  ll wc = (w * (w + 1) / 2) % mod;
  return (hc * wc) % mod;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int n;
  cin >> n;
  map<int, pair<ll, ll>> index_dim_map;
  set<pair<ll, int>> height_index_set;

  {
    vector<ll> hv(n), wv(n);
    for (ll& h : hv) cin >> h;
    for (ll& w : wv) cin >> w;
    for (int i = 0; i < n; i++) {
      if (i != n + 1 && hv[i] == hv[i + 1]) {
        wv[i + 1] += wv[i];
        continue;
      }
      index_dim_map[i] = {hv[i], wv[i]};
      height_index_set.insert({-hv[i], i});
    }
  }
  ll res = 0;

  while (height_index_set.size() > 1) {
    auto _it = height_index_set.begin();
    int ind_curr = _it->second;
    height_index_set.erase(_it);

    // should always be the iterator at key ind_curr
    auto curr_it = index_dim_map.lower_bound(ind_curr);
    assert(curr_it->first == ind_curr);
    auto [h_curr, w_curr] = index_dim_map[ind_curr];
    ll h_prev = 0, w_prev = 0, h_next = 0, w_next = 0;
    int ind_prev = -1, ind_next = -1;

    auto first_it = index_dim_map.begin();
    auto last_it = index_dim_map.end();

    last_it--;
    if (curr_it != last_it) {
      auto next_it = curr_it;
      next_it++;
      ind_next = next_it->first;
      tie(h_next, w_next) = next_it->second;
    }
    if (curr_it != first_it) {
      auto prev_it = curr_it;
      prev_it--;
      ind_prev = prev_it->first;
      tie(h_prev, w_prev) = prev_it->second;
    }
    assert(h_curr > h_prev);
    assert(h_curr > h_next);

    res += solve_rect(h_curr, w_curr);
    res %= mod;
    index_dim_map.erase(curr_it);

    if (h_prev > h_next) {
      res -= solve_rect(h_prev, w_curr);
      res += mod;
      res %= mod;
      index_dim_map[ind_prev].second = (w_prev + w_curr) % mod;
    }
    else if (h_next > h_prev) {
      res -= solve_rect(h_next, w_curr);
      res += mod;
      res %= mod;
      index_dim_map[ind_next].second = (w_next + w_curr) % mod;
    }
    else {
      res -= solve_rect(h_prev, w_curr);
      res += mod;
      res %= mod;
      index_dim_map[ind_prev].second = (w_prev + w_curr + w_next) % mod;
      height_index_set.erase({-h_next, ind_next});
      index_dim_map.erase(ind_next);
    }
  }
  assert(height_index_set.size() == 1);
  assert(index_dim_map.size() == 1);
  auto [h, w] = index_dim_map.begin()->second;
  res += solve_rect(h, w);
  res %= mod;
  cout << res;
}

• 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