Submission #1264324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264324		trufanov.p	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	51 ms	4316 KiB

fancyfence

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <string>
#include <queue>
#include <unordered_set>
#include <deque>
#include <numeric>
#include <cmath>
#include <unordered_map>
#include <set>
#include <stack>

using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long ll;

template <int Mod>
class ModInt {
private:
	int x;
	int __add(int a, int b) const {
		return (a + b < Mod ? a + b : a + b - Mod);
	}
	int __sub(int a, int b) const {
		return __add(a - b, Mod);
	}
	int __mul(int a, int b) const {
		ll a_ = a, b_ = b, Mod_ = Mod;
		return static_cast<int>((a_ * b_) % Mod_);
	}
	int __pow(int a, int b) const {
		int res = 1;
		int pw = a;
		while (b) {
			if (b & 1) {
				res = __mul(res, pw);
			}
			pw = __mul(pw, pw);
			b /= 2;
		}
		return res;
	}
	int __inv(int a) const {
		return __pow(a, Mod - 2);
	}
	int __div(int a, int b) const {
		return __mul(a, __inv(b));
	}
public:
	ModInt() :x(0) {}
	template <typename U, std::enable_if_t<std::is_convertible_v<U, int>, int> = 0>
	ModInt(U x_) : x(static_cast<int>(x_)) {}
	ModInt operator +(const ModInt& other) const {
		return ModInt(__add(x, other.x));
	}
	ModInt& operator +=(const ModInt& other) {
		x = __add(x, other.x);
		return *this;
	}
	ModInt operator -(const ModInt& other) const {
		return ModInt(__sub(x, other.x));
	}
	ModInt& operator -=(const ModInt& other) {
		x = __sub(x, other.x);
		return *this;
	}
	ModInt operator *(const ModInt& other) const {
		return ModInt(__mul(x, other.x));
	}
	ModInt& operator *=(const ModInt& other) {
		x = __mul(x, other.x);
		return *this;
	}
	ModInt operator /(const ModInt& other) const {
		return ModInt(__div(x, other.x));
	}
	ModInt& operator /=(const ModInt& other) {
		x = __div(x, other.x);
		return *this;
	}
	ModInt pow(const ModInt& other) const {
		return ModInt(pow(x, other.x));
	}
	ModInt operator +() const {
		return ModInt<Mod>(x);
	}
	ModInt operator -() const {
		return ModInt<Mod>(0) - *this;
	}
	bool operator ==(const ModInt& other) const {
		return x == other.x;
	}
	bool operator !=(const ModInt& other) const {
		return x != other.x;
	}
	friend istream& operator >>(istream& in, ModInt<Mod>& val) {
		in >> val.x;
		return in;
	}
	friend ostream& operator <<(ostream& out, const ModInt<Mod>& val) {
		out << val.x;
		return out;
	}
};

template <int Mod>
class DSU {
private:
	struct Group {
		ModInt<Mod> ans, rectbottom;
		ModInt<Mod> dx;
		int lasth;
		Group() :ans(0), rectbottom(0), dx(0), lasth(0) {}
	};
	int n;
	vector<int> p, d;
	vector<Group> info;
	int get_par(int v) {
		if (v == p[v]) {
			return v;
		}
		return p[v] = get_par(p[v]);
	}
public:
	DSU(int n_):n(n_) {
		p.resize(n);
		iota(p.begin(), p.end(), 0);
		d.resize(n);
		info.resize(n);
	}
	void setInfo(int i, ll w, int h) {
		info[i].dx = ModInt<Mod>(w);
		info[i].lasth = h;
	}
	void updateInfo(int i, int h) {
		i = get_par(i);
		ModInt<Mod> dh(info[i].lasth - h);
		info[i].ans += info[i].rectbottom * dh + info[i].dx * (info[i].dx + 1) * dh * (dh + 1) / ModInt<Mod>(4);
		info[i].rectbottom += info[i].dx * (info[i].dx + 1) * dh / ModInt<Mod>(2);
		info[i].lasth = h;
	}
	void unite(int i, int j) {
		i = get_par(i);
		j = get_par(j);
		if (i != j) {
			if (d[i] > d[j]) {
				swap(i, j);
			}
			p[i] = j;
			if (d[i] == d[j]) {
				d[j]++;
			}
			info[j].ans += info[i].ans;
			info[j].rectbottom += info[i].rectbottom;
			info[j].dx += info[i].dx;
		}
	}
	ModInt<Mod> get_answer(int i) {
		return info[get_par(i)].ans;
	}
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
	const int Mod = 1e9 + 7;
	int n;
	cin >> n;
	vector<int> h(n), w(n);
	for (int i = 0; i < n; ++i) {
		cin >> h[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> w[i];
	}
	vector<pair<int, int>> ev(n);
	for (int i = 0; i < n; ++i) {
		ev[i] = { h[i], i };
	}
	sort(ev.begin(), ev.end(), [&](const pair<int, int>& a, const pair<int, int>& b) -> bool {
		return a.first > b.first;
	});
	vector<bool> active(n);
	DSU<Mod> d(n);
	for (auto& e : ev) {
		int ind = e.second;
		active[ind] = true;
		d.setInfo(ind, w[ind], h[ind]);
		if (ind > 0 && active[ind - 1]) {
			d.updateInfo(ind - 1, h[ind]);
			d.unite(ind, ind - 1);
		}
		if (ind < n - 1 && active[ind + 1]) {
			d.updateInfo(ind + 1, h[ind]);
			d.unite(ind, ind + 1);
		}
	}
	d.updateInfo(0, 0);
	cout << d.get_answer(0) << '\n';
}

• 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