Submission #788627

#	Time	Username	Problem	Language	Result	Execution time	Memory
788627		WLZ	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	100 ms	16360 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;

const long long MOD = (long long) 1e9 + 7;

class dsu {
  private:
    vector<int> p, rank;
    vector<long long> sz;
  public:
    dsu(int n, const vector<long long> &_sz) : sz(_sz) {
      p.assign(n, -1);
      rank.assign(n, 0);
    }

    int root(int x) {
      if (p[x] == -1) {
        return x;
      }
      return (p[x] = root(p[x]));
    }

    bool same_set(int x, int y) {
      return (root(x) == root(y));
    }

    void connect(int x, int y) {
      x = root(x); y = root(y);
      if (x != y) {
        if (rank[x] > rank[y]) {
          p[y] = x;
          sz[x] = (sz[y] + sz[x]) % MOD;
        } else {
          p[x] = y;
          sz[y] = (sz[x] + sz[y]) % MOD;
          if (rank[x] == rank[y]) {
            rank[y]++;
          }
        }
      }
    }

    long long st_sz(int x) {
      return sz[root(x)];
    }
};

long long modpow(long long b, long long p) {
  if (p == 0) {
    return 1;
  }
  long long ans = modpow((b * b) % MOD, p / 2);
  if (p % 2 == 1) {
    ans = (ans * b) % MOD;
  }
  return ans;
}
 
long long inv(long long x) {
  return modpow(x, MOD - 2);
}
 
long long mul(long long a, long long b) {
  return (a * b) % MOD;
}


long long f(long long h, long long w) {
  return mul(h, mul(h + 1, mul(w, mul(w + 1, inv(4)))));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<long long> h(n), w(n);
  map<long long, vector<long long>, greater<long long> > mp;
  for (int i = 0; i < n; i++) {
    cin >> h[i];
    mp[h[i]].push_back(i);
  }
  for (int i = 0; i < n; i++) {
    cin >> w[i];
  }
  dsu g(n, w);
  vector<bool> b(n, false);
  long long ans = 0;
  for (auto& p : mp) {
    for (auto& x : p.second) {
      b[x] = true;
      if (x > 0 && b[x - 1] && !g.same_set(x, x - 1)) {
        ans = ((ans - f(p.first, g.st_sz(x - 1))) % MOD + MOD) % MOD;
        g.connect(x, x - 1);
      }
      if (x < n - 1 && b[x + 1] && !g.same_set(x, x + 1)) {
        ans = ((ans - f(p.first, g.st_sz(x + 1))) % MOD + MOD) % MOD;
        g.connect(x, x + 1);
      }
      ans = (ans + f(p.first, g.st_sz(x))) % MOD;
    }
  }
  cout << ans << '\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