Submission #848332

#	Time	Username	Problem	Language	Result	Execution time	Memory
848332		lovrot	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	27 ms	3916 KiB

fancyfence

#include <cstdio> 
#include <stack> 
#include <vector> 

#define X first
#define Y second
#define pb push_back

using namespace std; 

typedef long long ll; 
typedef pair<int, int> pii; 

const int MOD = 1e9 + 7; 
const int N = 1e5 + 10;

inline int add(int a, int b) {
	return ((ll) a + b + MOD) % MOD; 
}

inline int mult(int a, int b) {
	return (ll) a * b % MOD; 
}

inline int frac(int a) {
	return ((ll) a * (a + 1) / 2) % MOD;
}

int n, H[N], W[N];
int sol, sum;
stack<pii> stog; 

int product(int h, int w) {
	return mult(w, frac(h)); 
} 

int calc(int h, int w) {
	return mult(frac(w), frac(h)); 
}

int _calc(int h, int w1, int w2) {
	return mult(mult(w1, w2), frac(h)); 
}

int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%d", H + i);
	for(int i = 0; i < n; i++) scanf("%d", W + i);
	for(int i = 0; i < n; i++) {
		sol = add(sol, calc(H[i], W[i])); //printf("+= %d\n", calc(H[i], W[i]));
		int _w = 0; 
		while(!stog.empty() && stog.top().X >= H[i]) {
			int h = stog.top().X;
			int w = stog.top().Y;
			sum = add(sum, -product(h, w)); 
			_w = add(_w, w); 
			stog.pop(); 
		}
		sol = add(sol, mult(sum, W[i])); 
		sol = add(sol, _calc(H[i], _w, W[i])); 
		_w = add(W[i], _w);
		stog.push({H[i], _w}); 
		sum = add(sum, product(H[i], _w)); 
	}	
	printf("%d\n", sol);
	return 0;
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
fancyfence.cpp:47:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  for(int i = 0; i < n; i++) scanf("%d", H + i);
      |                             ~~~~~^~~~~~~~~~~~~
fancyfence.cpp:48:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  for(int i = 0; i < n; i++) scanf("%d", W + i);
      |                             ~~~~~^~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27