oj.uz

Submission #954429

# Submission time Handle Problem Language Result Execution time Memory
954429 2024-03-27T21:17:08 Z MinaRagy06 Fancy Fence (CEOI20_fancyfence) C++17
30 / 100
 1000 ms 2396 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int mod = 1e9 + 7;
struct mint {
	int v;
	mint() {
		v = 0;
	}
	mint(ll x) {
		if (x >= mod) {
			v = x % mod;
		} else {
			v = x;
		}
	}
	mint& operator+=(const mint &b) {
		if ((v += b.v) >= mod) {
			v -= mod;
		}
		return *this;
	}
	friend mint operator+(mint a, mint b) {
		return a += b;
	}
	mint& operator*=(const mint &b) {
		v = 1ll * v * b.v % mod;
		return *this;
	}
	friend mint operator*(mint a, mint b) {
		return a *= b;
	}
	mint power(mint a, int b) {
		mint ans = 1;
		while (b) {
			if (b & 1) {
				ans *= a;
			}
			a *= a, b >>= 1;
		}
		return ans;
	}
	mint& operator/=(const mint &b) {
		v = 1ll * v * power(b, mod - 2).v % mod;
		return *this;
	}
	friend mint operator/(mint a, mint b) {
		return a /= b;
	}
	friend ostream& operator<<(ostream &os, mint a) {
		return os << a.v;
	}
	friend istream& operator>>(istream &is, mint &a) {
		return is >> a.v;
	}
};
const int N = 100'005;
struct segtree {
	mint leaf[N];
	segtree() {
		for (int i = 0; i < N; i++) {
			leaf[i] = 1;
		}
	}
	void mult(int l, int r, mint v) {
		for (int i = l; i <= r; i++) {
			leaf[i] *= v;
		}
	}
	mint get(int l, int r) {
		mint s = 0;
		for (int i = l; i <= r; i++) {
			s += leaf[i];
		}
		return s;
	}
} seg, seg2;
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n;
	cin >> n;
	int h[n + 1], w[n];
	for (int i = 0; i < n; i++) {
		cin >> h[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> w[i];
	}
	h[n] = -2e9;
	stack<int> s;
	s.push(n);
	mint ans = 0;
	for (int l = n - 1; l >= 0; l--) {
		while (h[l] <= h[s.top()]) {
			int st = s.top();
			s.pop();
			int en = s.top() - 1;
			mint v = mint(h[l]) / h[st];
			seg.mult(st, en, v);
			seg2.mult(st, en, v * v);
		}
		ans += (mint(w[l]) * (w[l] + 1) / 2) * (mint(h[l]) * (h[l] + 1) / 2);
		mint sum = seg.get(l + 1, n - 1) + seg2.get(l + 1, n - 1);
		sum *= w[l] / mint(2);
		ans += sum;
		s.push(l);
		seg.mult(l, l, mint(h[l]) * w[l]);
		seg2.mult(l, l, mint(h[l]) * h[l] * w[l]);
	}
	cout << ans << '\n';
	return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 3 ms 1372 KB Output is correct
3 Execution timed out 1070 ms 1372 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1112 KB Output is correct
2 Correct 266 ms 1296 KB Output is correct
3 Execution timed out 1064 ms 2396 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 4 ms 1116 KB Output is correct
3 Correct 264 ms 1296 KB Output is correct
4 Execution timed out 1020 ms 2392 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1112 KB Output is correct
8 Correct 3 ms 1116 KB Output is correct
9 Correct 4 ms 1252 KB Output is correct
10 Correct 5 ms 1116 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 3 ms 1112 KB Output is correct
14 Correct 3 ms 1116 KB Output is correct
15 Correct 3 ms 1116 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 3 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 4 ms 1116 KB Output is correct
11 Execution timed out 1062 ms 1628 KB Time limit exceeded
12 Halted 0 ms 0 KB -