oj.uz

Submission #959887

# Submission time Handle Problem Language Result Execution time Memory
959887 2024-04-09T09:20:52 Z penguin133 Fancy Fence (CEOI20_fancyfence) C++17
43 / 100
 67 ms 12888 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[1000005], W[1000005], P[1000005];
stack <pi> s;
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:107:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  107 | main(){
      | ^~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 31 ms 6792 KB Output is correct
4 Correct 59 ms 8788 KB Output is correct
5 Correct 60 ms 8712 KB Output is correct
6 Correct 65 ms 9112 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 7 ms 4628 KB Output is correct
3 Correct 34 ms 6736 KB Output is correct
4 Correct 66 ms 8788 KB Output is correct
5 Runtime error 21 ms 12888 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 4696 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 7 ms 4440 KB Output is correct
4 Correct 35 ms 6780 KB Output is correct
5 Correct 67 ms 8796 KB Output is correct
6 Runtime error 22 ms 12884 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 4440 KB Output is correct
2 Correct 6 ms 10332 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 5 ms 10076 KB Output is correct
11 Correct 1 ms 5208 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 5 ms 10332 KB Output is correct
14 Correct 2 ms 4700 KB Output is correct
15 Correct 2 ms 4696 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 5 ms 10328 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 5 ms 10336 KB Output is correct
5 Correct 1 ms 4696 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 30 ms 6748 KB Output is correct
12 Correct 60 ms 8796 KB Output is correct
13 Correct 60 ms 8784 KB Output is correct
14 Correct 60 ms 8656 KB Output is correct
15 Correct 2 ms 4440 KB Output is correct
16 Correct 7 ms 4440 KB Output is correct
17 Correct 34 ms 6748 KB Output is correct
18 Correct 65 ms 8792 KB Output is correct
19 Runtime error 21 ms 12884 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -