oj.uz

Submission #746087

# Submission time Handle Problem Language Result Execution time Memory
746087 2023-05-21T11:37:36 Z vjudge1 Fancy Fence (CEOI20_fancyfence) C++17
42 / 100
 88 ms 16340 KB 
#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;

  auto log = [&]() {
    for (auto& [i, dim] : index_dim_map) {
      cout << i << ": " << dim.first << " " << dim.second << endl;
    }
    cout << endl;
  };

  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];
    int 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_curr;
    }
    else if (h_next > h_prev) {
      res -= solve_rect(h_next, w_curr);
      res += mod;
      res %= mod;
      index_dim_map[ind_next].second += w_curr;
    }
    else {
      res -= solve_rect(h_prev, w_curr);
      res += mod;
      res %= mod;
      index_dim_map[ind_prev].second += w_curr + w_next;
      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;
}

Compilation message

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:36:8: warning: variable 'log' set but not used [-Wunused-but-set-variable]
   36 |   auto log = [&]() {
      |        ^~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 316 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 11 ms 1116 KB Output is correct
4 Correct 23 ms 1908 KB Output is correct
5 Correct 21 ms 1876 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 476 KB Output is correct
4 Correct 10 ms 1108 KB Output is correct
5 Correct 18 ms 1876 KB Output is correct
6 Correct 28 ms 1876 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 8 ms 1876 KB Output is correct
9 Correct 23 ms 4556 KB Output is correct
10 Correct 88 ms 16120 KB Output is correct
11 Correct 78 ms 16340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Incorrect 1 ms 324 KB Output isn't correct
11 Halted 0 ms 0 KB -