oj.uz

Submission #397128

# Submission time Handle Problem Language Result Execution time Memory
397128 2021-05-01T14:02:40 Z Sohsoh84 Fancy Fence (CEOI20_fancyfence) C++14
15 / 100
 91 ms 17020 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;
const ll INV2 = 500000004;

ll L[MAXN], H[MAXN], W[MAXN];
set<pll> st;

inline void mkey(ll& a) {
	if (a >= MOD) a -= MOD;
	if (a < 0) a += MOD;
}

inline ll C2(ll a) {
	a %= MOD;
	return a * (a - 1) % MOD * INV2 % MOD;;
} 

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	vector<int> v;
	for (int i = 1; i <= n; i++) {
		cin >> H[i];
		v.push_back(i);
	}

	L[0] = 1;
	ll tot = 0;
	for (int i = 1; i <= n; i++) {
		cin >> W[i];
		L[i] = L[i - 1] + W[i - 1];
		tot += W[i];
	}

	ll T = C2(tot + 1);
	st.insert({1, tot});

	sort(all(v), [] (int i, int j) {
		return H[i] < H[j];		
	});


	ll lst = 0, ans = 0;
	for (int e : v) {
		mkey(ans += T * (C2(H[e] + 1) - C2(lst + 1) + MOD) % MOD);
		ll l = L[e], r = l + W[e] - 1;
		auto it = st.upper_bound(make_pair(l, INF));
		it--;
		ll tl = it -> X, tr = it -> Y;
		mkey(T -= C2(tr - tl + 2));
		ll m_r = l - 1, m_l = r + 1;
		
		if (m_r >= tl) {
			mkey(T += C2(m_r - tl + 2));
			st.insert({tl, m_r});
		} 

		if (m_l <= tr) {
			mkey(T += C2(tr - m_l + 2));
		       	st.insert({m_l, tr});	
		}

		lst = H[e];
	}

	cout << ans << endl;
	return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 2 ms 460 KB Output isn't correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 460 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 460 KB Output is correct
2 Correct 6 ms 1488 KB Output is correct
3 Correct 29 ms 5988 KB Output is correct
4 Correct 76 ms 16912 KB Output is correct
5 Correct 78 ms 17020 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 6 ms 1484 KB Output is correct
4 Correct 31 ms 6116 KB Output is correct
5 Correct 75 ms 16868 KB Output is correct
6 Correct 91 ms 16972 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 7 ms 1356 KB Output is correct
9 Correct 38 ms 7532 KB Output is correct
10 Incorrect 67 ms 11064 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

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

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 2 ms 460 KB Output isn't correct