oj.uz

Submission #959938

# Submission time Handle Problem Language Result Execution time Memory
959938 2024-04-09T10:38:39 Z penguin133 Fancy Fence (CEOI20_fancyfence) C++17
28 / 100
 54 ms 10436 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], A[100005];
stack <pi> s;
const int mod = 1e9 + 7;
vector <int> v;
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 = v[e] * (v[e] + 1) / 2;
			brr %= mod;
			int brr2 = v[s] * (v[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){
		if(a > b)return 0;
		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;
	v.push_back(1e9);
	v.push_back(0);
	for(int i = 1; i <= n; i++)cin >> H[i], v.push_back(H[i]), v.push_back(H[i] + 1);
	for(int i = 1; i <= n; i++)cin >> W[i];
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	root = new node(0, (int)v.size());
	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;
		int x = lower_bound(v.begin(), v.end(), H[i] + 1) - v.begin();
		root->upd(x, (int)v.size(), 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();
		x--;
		int tot = root->qry(1, x);
		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:116:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  116 | main(){
      | ^~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 12.0

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

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 27 ms 8384 KB Output is correct
4 Correct 52 ms 9676 KB Output is correct
5 Correct 52 ms 9856 KB Output is correct
6 Correct 54 ms 9964 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 6 ms 5088 KB Output is correct
3 Correct 27 ms 8664 KB Output is correct
4 Correct 54 ms 10160 KB Output is correct
5 Correct 51 ms 10184 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4560 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 6 ms 5088 KB Output is correct
4 Correct 28 ms 8596 KB Output is correct
5 Correct 54 ms 10184 KB Output is correct
6 Correct 54 ms 10436 KB Output is correct
7 Incorrect 3 ms 4696 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 3 ms 4700 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 4440 KB Output is correct
2 Incorrect 2 ms 4700 KB Output isn't correct
3 Halted 0 ms 0 KB -