Submission #746946

#	Time	Username	Problem	Language	Result	Execution time	Memory
746946		vjudge1	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	161 ms	16336 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;
  set<pair<ll, int>> height_index_set;
  map<int, pair<ll, ll>> index_dim_map;

  height_index_set.insert({0, -1});
  height_index_set.insert({0, n});
  index_dim_map[-1] = {0, 0};
  index_dim_map[n] = {0, 0};

  {
    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);
    auto& [h_curr, w_curr] = index_dim_map[ind_curr];
    assert(curr_it->first == ind_curr);

    auto next_it = curr_it;
    next_it++;
    auto& [h_next, w_next] = next_it->second;

    auto prev_it = curr_it;
    prev_it--;
    auto& [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;

    if (h_prev > h_next) {
      res -= solve_rect(h_prev, w_curr);
      res += mod;
      res %= mod;
      w_prev += w_curr;
      w_prev %= mod;
    }
    else if (h_next > h_prev) {
      res -= solve_rect(h_next, w_curr);
      res += mod;
      res %= mod;
      w_next += w_curr;
      w_next %= mod;
    }
    else {
      res -= solve_rect(h_prev, w_curr);
      res += mod;
      res %= mod;
      w_prev += w_curr + w_next;
      w_prev %= mod;
      height_index_set.erase({-h_next, next_it->first});
      index_dim_map.erase(next_it);
    }
    index_dim_map.erase(curr_it);
  }
  assert(height_index_set.size() == 1);
  assert(index_dim_map.size() == 1);
  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