oj.uz

Submission #944854

# Submission time Handle Problem Language Result Execution time Memory
944854 2024-03-13T06:45:02 Z oolimry Fancy Fence (CEOI20_fancyfence) C++17
12 / 100
 1 ms 856 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define h first
#define w second
using namespace std;
typedef long long lint;
typedef pair<lint,lint> ii;

lint H[100005];
lint W[100005];
lint mod = 1000000007;

void fix(lint &x){
	x %= mod;
	if(x < 0) x += mod;
}

lint within(lint h, lint w){
	lint A = h * (h+1) / 2;
	fix(A);
	
	lint B = w * (w + 1) / 2;
	fix(B);
	
	return (A*B)%mod;
}

lint acc = 0; ///sum of h*(h+1)*w of previous blocks
lint ans = 0; 

vector<ii> S;

lint cal(lint h, lint w){
	lint toadd = h*(h+1)/2;
	fix(toadd);
	toadd *= w;
	fix(toadd);
	return toadd;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n; cin >> n;
	
	for(int i = 0;i < n;i++) cin >> H[i];
	for(int i = 0;i < n;i++) cin >> W[i];	
	
	for(int i = 0;i < n;i++){
		lint h = H[i], w = W[i];
		assert(w == 1);
		
		lint popWidth = 0;
		while(!S.empty()){
			ii T = S.back();
			if(T.h > h){
				popWidth += T.w;
				S.pop_back();
				acc -= cal(T.h, T.w);
				fix(acc);
			}
			else break;
		}
		
		fix(popWidth);
		
		acc += cal(h, popWidth);
		fix(acc);
		
		ans += acc * w;
		ans += within(h,w);
		fix(ans);
		
		popWidth += w;
		fix(popWidth);
		
		S.push_back(ii(h, popWidth));
		acc += cal(h,w);
		fix(acc);
		
	}
	
	cout << ans << "\n";
	
}

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -