oj.uz

Submission #959883

# Submission time Handle Problem Language Result Execution time Memory
959883 2024-04-09T09:19:03 Z penguin133 Fancy Fence (CEOI20_fancyfence) C++17
43 / 100
 65 ms 8284 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pi pair <int, int> 
#define pii pair <int, pi>

int n, H[100005], W[100005], P[100005];
stack <pi> s;
int lst[105];
const int mod = 1e9 + 7;

struct node{
	int s, e, m, val, lz, val2;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		val = lz = val2 = 0;
		l = r = nullptr;
	}
	
	void mc(){
		if(s == e || l != nullptr)return;
		l = new node(s, m);
		r = new node(m+1, e);
	}
	
	void prop(){
		if(lz){
			int brr = e * (e + 1) / 2;
			brr %= mod;
			int brr2 = s * (s - 1) / 2;
			brr2 %= mod;
			brr = (brr - brr2 + mod) % mod;
			val = lz * (brr) % mod;
			if(s != e){
				mc();
				l->lz = lz; r->lz = lz;
			}
			lz = 0;
		}
	}
	
	void upd(int a, int b, int c){
		prop();
		if(a == s && b == e)lz = c;
		else{
			mc();
			if(b <= m)l->upd(a, b, c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b, c);
			l->prop(), r->prop();
			val = l->val + r->val;
			val %= mod;
		}
	}
	
	int qry(int a, int b){
		prop();
		if(a == s && b == e)return val;
		if(l == nullptr)return 0;
		if(b <= m)return l->qry(a, b);
		if(a > m)return r->qry(a, b);
		return (l->qry(a, m) + r->qry(m+1, b)) % mod;
	}
}*root;

void solve(){
	cin >> n;
	for(int i = 1; i <= n; i++)cin >> H[i];
	for(int i = 1; i <= n; i++)cin >> W[i];
	s.push({0, 0});
	int ans = 0;
	root = new node(0, 1e9);
	for(int i = 1; i <= n; i++){
		P[i] = P[i - 1] + W[i];
		P[i] %= mod;
		root->upd(H[i] + 1, 1e9, P[i]);
		//for(int j = H[i] + 1; j <= 100; j++)lst[j] = P[i];
		/*
		for(int j = 1; j <= H[i]; j++){
			ans += j * W[i] % mod * (P[i - 1] - lst[j] + mod) % mod;
			ans %= mod;
		}
		*/
		root->prop();
		int tot = root->qry(1, H[i]);
		int tot2 = H[i] * (H[i] + 1) / 2;
		tot2 %= mod;
		tot2 *= P[i - 1];
		tot2 %= mod;
		tot2 -= tot;
		tot2 = (tot2 + mod) % mod;
		ans += tot2 * W[i] % mod;
		ans %= mod;
		int a = W[i] * (W[i] + 1) / 2;
		a %= mod;
		int b = H[i] * (H[i] + 1) / 2;
		b %= mod;
		ans += (a * b % mod);
		ans %= mod;
		//cout << ans << '\n';
	}
	cout << ans;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	while(tc--)solve();
}

Compilation message

fancyfence.cpp:108:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  108 | main(){
      | ^~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 30 ms 2648 KB Output is correct
4 Correct 58 ms 2648 KB Output is correct
5 Correct 63 ms 2652 KB Output is correct
6 Correct 59 ms 2648 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 7 ms 2652 KB Output is correct
3 Correct 36 ms 3584 KB Output is correct
4 Correct 65 ms 4692 KB Output is correct
5 Runtime error 18 ms 7004 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 9 ms 2652 KB Output is correct
4 Correct 33 ms 3420 KB Output is correct
5 Correct 65 ms 4700 KB Output is correct
6 Runtime error 18 ms 6992 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2528 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 5 ms 8028 KB Output is correct
11 Correct 1 ms 3164 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 6 ms 8276 KB Output is correct
14 Correct 2 ms 2652 KB Output is correct
15 Correct 2 ms 2648 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 5 ms 8284 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 5 ms 8116 KB Output is correct
5 Correct 1 ms 2512 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 2544 KB Output is correct
11 Correct 30 ms 3164 KB Output is correct
12 Correct 59 ms 3932 KB Output is correct
13 Correct 60 ms 3924 KB Output is correct
14 Correct 60 ms 3920 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 7 ms 2648 KB Output is correct
17 Correct 41 ms 3416 KB Output is correct
18 Correct 65 ms 4692 KB Output is correct
19 Runtime error 17 ms 6996 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -