oj.uz

Submission #959914

# Submission time Handle Problem Language Result Execution time Memory
959914 2024-04-09T10:11:01 Z penguin133 Fancy Fence (CEOI20_fancyfence) C++17
58 / 100
 269 ms 262144 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){
      if(a>b)return;
		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 4444 KB Output is correct
2 Correct 6 ms 10208 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 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 2 ms 4444 KB Output is correct
2 Correct 3 ms 4440 KB Output is correct
3 Correct 34 ms 7204 KB Output is correct
4 Correct 66 ms 10252 KB Output is correct
5 Correct 67 ms 9808 KB Output is correct
6 Correct 67 ms 9808 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 10 ms 4700 KB Output is correct
3 Correct 37 ms 7508 KB Output is correct
4 Correct 73 ms 10576 KB Output is correct
5 Correct 19 ms 10832 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 8 ms 4844 KB Output is correct
4 Correct 38 ms 7740 KB Output is correct
5 Correct 72 ms 10780 KB Output is correct
6 Correct 23 ms 10824 KB Output is correct
7 Correct 5 ms 10072 KB Output is correct
8 Correct 38 ms 50260 KB Output is correct
9 Correct 84 ms 99048 KB Output is correct
10 Correct 269 ms 259468 KB Output is correct
11 Runtime error 232 ms 262144 KB Execution killed with signal 9
12 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 4440 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 5 ms 10076 KB Output is correct
11 Correct 1 ms 5212 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 4700 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 6 ms 10208 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 5 ms 10204 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4440 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 4568 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 35 ms 7260 KB Output is correct
12 Correct 66 ms 9996 KB Output is correct
13 Correct 68 ms 9808 KB Output is correct
14 Correct 69 ms 9816 KB Output is correct
15 Correct 2 ms 4444 KB Output is correct
16 Correct 8 ms 4700 KB Output is correct
17 Correct 37 ms 7628 KB Output is correct
18 Correct 71 ms 10648 KB Output is correct
19 Correct 23 ms 10844 KB Output is correct
20 Correct 5 ms 10076 KB Output is correct
21 Correct 37 ms 50280 KB Output is correct
22 Correct 83 ms 99156 KB Output is correct
23 Correct 245 ms 259588 KB Output is correct
24 Runtime error 229 ms 262144 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -