oj.uz

Submission #945692

# Submission time Handle Problem Language Result Execution time Memory
945692 2024-03-14T06:28:19 Z WongYiKai Fancy Fence (CEOI20_fancyfence) C++14
30 / 100
 25 ms 4444 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n;
	ll m = 1000000007;
	cin >> n;
	ll h[n+5],w[n+5];
	ll prefw[n+5];
	ll w2 = 0;
	for (int i=0;i<n;i++){
		ll temp;
		cin >> temp;
		h[i] = temp;
	}
	for (int i=0;i<n;i++){
		ll temp;
		cin >> temp;
		w[i] = temp;
		w2 += temp;
		//w2%=m;
		prefw[i] = w2;
	}
	stack<pair<ll,ll>> s;
	ll total=0;
	for (int i=0;i<n;i++){
		ll num=0;
		ll carry=0;
		while (!s.empty() && h[s.top().first]>h[i]){
			s.pop();
		}
		if (!s.empty()){
			carry += s.top().second;
			carry%=m;
			//cout << carry << " ";
			ll height = h[i]-h[s.top().first];
			ll width = prefw[i]-prefw[s.top().first]-w[i];
			width%=m;
			height = height*(height+1)/2;
			height%=m;
			carry += (height*width)%m;
			carry%=m;
		}
		else{
			ll height = h[i];
			ll width = prefw[i]-w[i];
			width%=m;
			height = height*(height+1)/2;
			height%=m;
			carry += (height*width)%m;
			carry%=m;
		}
		//cout << carry << " ";
		ll height = h[i];
		ll width = w[i];
		num += (carry*width)%m;
		num%=m;
		height = height*(height+1)/2;
		ll w2 = width*(width+1)/2;
		height%=m;
		w2%=m;
		num += (height*w2)%m;
		num%=m;
		carry += (height*width)%m;
		carry%=m;
		s.push({i,carry});
		total += num;
		total %=m;
	}
	cout << total%m;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 836 KB Output is correct
3 Correct 9 ms 2396 KB Output is correct
4 Correct 25 ms 4176 KB Output is correct
5 Correct 20 ms 4184 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #5
15.0 / 15.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 2 ms 856 KB Output is correct
4 Correct 9 ms 2396 KB Output is correct
5 Correct 19 ms 4332 KB Output is correct
6 Correct 19 ms 4444 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 10 ms 2396 KB Output is correct
10 Correct 19 ms 4444 KB Output is correct
11 Correct 18 ms 4444 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #6
0 / 18.0

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

Subtask #7
0 / 27.0

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