Submission #842245

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

fancyfence

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

#include <iostream>

/**
 * Compute the greatest common divisor d of a and b together 
 * with the x and y such that ax + by = d using the extended Euclidean algorithm
 * 
 * @param integers a, b whose gcd will be computed, references x, y where values will be stored
 * @returns greatest common divisor of a and b
*/
template<typename T1, typename T2>
T1 extgcd(const T1& a, const T1& b, T2 &x, T2 &y) {
    x = 1; y = 0;
    T1 a1(a), b1(b);
    T2 x1 = 0, y1 = 1;
    while (b1 != 0) {
        T1 q = a1 / b1;
        tie(x, x1) = make_pair(x1, x - q * x1);
        tie(y, y1) = make_pair(y1, y - q * y1);
        tie(a1, b1) = make_pair(b1, a1 - q * b1);
    }
    return a1;
}

/**
 * Modular integer implementation
 * NOT completely tested!
*/
template<const int MOD>
class modint {
    private: int x;

    public:
    modint() : x(0) {}

    template<typename T>
    void set(const T _x, bool raw = false) {
        if (raw) x = _x;
        else {
            x = _x % MOD;
            if (x < 0) x += MOD;
        }
    }

    template<typename T>
    modint(const T &_x, bool raw = false) {
        set(_x, raw);
    }

    template<typename T>
    modint<MOD> &operator=(const T &_x) {
        set(_x);
        return *this;
    }

    modint<MOD> &operator+=(const modint<MOD> &rhs) {
        x += rhs.x;
        if (x >= MOD) x -= MOD;
        return *this;
    }
        
    friend modint<MOD> operator+(modint<MOD> lhs, const modint<MOD> &rhs) {
        lhs += rhs;
        return lhs;
    }

    modint<MOD> &operator-=(const modint<MOD> &rhs) {
        x -= rhs.x;
        if (x < 0) x += MOD;
        return *this;
    }
        
    friend modint<MOD> operator-(modint<MOD> lhs, const modint<MOD> &rhs) {
        lhs -= rhs;
        return lhs;
    }

    modint<MOD> &operator*=(const modint<MOD> &rhs) {
        x = (unsigned long long) x * rhs.x % MOD;
        return *this;
    }

    friend modint<MOD> operator*(modint<MOD> lhs, const modint<MOD> &rhs) {
        lhs *= rhs;
        return lhs;
    }

    modint<MOD> inv() const {
        modint x1, y1;
        extgcd(x, MOD, x1, y1);
        return move(x1);
    }

    modint<MOD> &operator/=(const modint<MOD> &rhs) {
        operator*=(rhs.inv());
        return *this;
    }

    friend modint<MOD> operator/(modint<MOD> lhs, const modint<MOD> &rhs) {
        lhs /= rhs;
        return lhs;
    }

    modint<MOD> &operator++() {
        operator+=(1);
        return *this;
    }

    modint<MOD> operator++(int) {
        modint<MOD> old = *this;
        operator++();
        return old;
    }

    modint<MOD> &operator--() {
        operator-=(1);
        return *this;
    }

    modint<MOD> operator--(int) {
        modint<MOD> old = *this;
        operator--();
        return old;
    }

    template<typename T>
    operator T() const {
        return x;
    }

    int val() const {
        return x;
    }
};

template<const int MOD, typename T>
modint<MOD> pow(modint<MOD> a, T b) {
    modint<MOD> ans(1, true);
    while (b != 0) {
        if (b & 1) ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}

template<const int MOD>
std::istream &operator>>(std::istream &is, modint<MOD> &x) {
    unsigned int _x;
    is >> _x;
    x.set(_x, true);
    return is;
}

template<const int MOD>
std::ostream &operator<<(std::ostream &os, const modint<MOD> &x) {
    os << x.val();
    return os;
}

using mint1000000007 = modint<1000000007>;
using mint998244353 = modint<998244353>;

using mint = mint1000000007;

mint f(mint h, mint w) {
    return h * (h + 1) * w * (w + 1) / 4;
}

class dsu {
  private:
    vector<int> p, rank;
    vector<mint> sz;
  public:
    dsu(int n, const vector<mint> &_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];
        } else {
          p[x] = y;
          sz[y] += sz[x];
          if (rank[x] == rank[y]) {
            rank[y]++;
          }
        }
      }
    }

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

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

Compilation message (stderr)

fancyfence.cpp: In instantiation of 'modint<MOD> modint<MOD>::inv() const [with int MOD = 1000000007]':
fancyfence.cpp:97:24:   required from 'modint<MOD>& modint<MOD>::operator/=(const modint<MOD>&) [with int MOD = 1000000007]'
fancyfence.cpp:102:13:   required from 'modint<1000000007> operator/(modint<1000000007>, const modint<1000000007>&)'
fancyfence.cpp:169:40:   required from here
fancyfence.cpp:93:23: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
   93 |         return move(x1);
      |                       ^
fancyfence.cpp:93:23: note: remove 'std::move' call

• 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