oj.uz

Submission #704749

# Submission time Handle Problem Language Result Execution time Memory
704749 2023-03-02T22:55:04 Z Markomafko972 Fancy Fence (CEOI20_fancyfence) C++14
100 / 100
 51 ms 3808 KB 
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n;
pii p[100005];
stack<pii> s;

int add(int x, int y) {
	if (x+y < MOD) return x+y;
	return x+y-MOD;
}

int mul(int x, int y) {
	return (ll)x * (ll)y % MOD;
}

int pot(int x, int y) {
	if (y == 0) return 1;
	if (y == 1) return x;
	int out = pot(x, y/2);
	out = mul(out, out);
	if (y % 2 == 1) out = mul(out, x);
	return out;
}

int main () {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) cin >> p[i].X;
	for (int i = 0; i < n; i++) cin >> p[i].Y;
	
	int sol = 0;
	for (int i = 0; i <= n; i++) {
		int kol = 0;
		while (s.size() > 0 && s.top().X >= p[i].X) {
			ll h = add(p[i].X, 1);
			h = add(h, s.top().X);
			h = mul(h, s.top().X-p[i].X);
			h = mul(h, pot(2, MOD-2));
			//cout << h << " ";
			
			ll tren = add(kol, kol);
			tren = add(tren, s.top().Y);
			tren = add(tren, 1);
			tren = mul(tren, s.top().Y);
			tren = mul(tren, pot(2, MOD-2));
			//cout << tren << " ";
			tren = mul(tren, h);
			sol = add(sol, tren);
			//cout << s.top().X << " " << sol << endl;
			
			kol = add(kol, s.top().Y);
			s.pop();
		}
		kol = add(kol, p[i].Y);
		s.push({p[i].X, kol});
	}
	cout << sol;

	return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 352 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 19 ms 1236 KB Output is correct
4 Correct 38 ms 2260 KB Output is correct
5 Correct 38 ms 2132 KB Output is correct
6 Correct 38 ms 2252 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Correct 5 ms 596 KB Output is correct
3 Correct 21 ms 1620 KB Output is correct
4 Correct 42 ms 2304 KB Output is correct
5 Correct 44 ms 2308 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 5 ms 576 KB Output is correct
4 Correct 21 ms 1696 KB Output is correct
5 Correct 43 ms 2276 KB Output is correct
6 Correct 51 ms 2244 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 5 ms 596 KB Output is correct
9 Correct 22 ms 1844 KB Output is correct
10 Correct 43 ms 3116 KB Output is correct
11 Correct 42 ms 3144 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 1 ms 356 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 352 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 212 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 19 ms 1316 KB Output is correct
12 Correct 37 ms 2240 KB Output is correct
13 Correct 36 ms 2240 KB Output is correct
14 Correct 39 ms 2264 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 5 ms 556 KB Output is correct
17 Correct 22 ms 1624 KB Output is correct
18 Correct 41 ms 3028 KB Output is correct
19 Correct 44 ms 3124 KB Output is correct
20 Correct 1 ms 360 KB Output is correct
21 Correct 5 ms 596 KB Output is correct
22 Correct 22 ms 1852 KB Output is correct
23 Correct 44 ms 3808 KB Output is correct
24 Correct 42 ms 3732 KB Output is correct
25 Correct 0 ms 328 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 360 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 5 ms 600 KB Output is correct
31 Correct 5 ms 600 KB Output is correct
32 Correct 21 ms 1488 KB Output is correct
33 Correct 21 ms 1672 KB Output is correct
34 Correct 40 ms 2760 KB Output is correct
35 Correct 42 ms 2776 KB Output is correct
36 Correct 43 ms 3152 KB Output is correct
37 Correct 42 ms 3036 KB Output is correct
38 Correct 1 ms 336 KB Output is correct
39 Correct 41 ms 3020 KB Output is correct
40 Correct 42 ms 3040 KB Output is correct
41 Correct 41 ms 3028 KB Output is correct
42 Correct 41 ms 3376 KB Output is correct