Submission #1230809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230809		Bui_Quoc_Cuong	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	33 ms	2732 KiB

fancyfence

# include <bits/stdc++.h>
using namespace std;

int ko () {
    cerr << "Time used: " << 1.0 * clock() / CLOCKS_PER_SEC << "s ";
    return 0;
}

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

int n;
int h[N], w[N];

int Pow(int x, int y) {
	if (y == 0) return 1;
	if (y == 1) return x;
	int c = Pow(x, y / 2);
	if (y & 1) return 1LL * c * c % MOD * x % MOD;
	else return 1LL * c * c % MOD;
}

namespace sub5 {
	inline int SumnC2(int x) {
		return 1LL * x * (x + 1) % MOD * Pow(2, MOD - 2) % MOD;
	}

	void solve() {	
		int ans = 0;

		for (int i = 1; i <= n; i++) {
			int H = h[i];
			(ans+= 1LL * SumnC2(H) * SumnC2(w[i]) % MOD) %= MOD;
			for (int j = i - 1; j >= 1; j--) {
				H = min(H, h[j]);
				(ans+= 1LL * SumnC2(H) * w[j] % MOD * w[i] % MOD) %= MOD;
			}
		}

		cout << ans;
	}	
}

namespace sub6 {
	inline int SumnC2(int x) {
		return 1LL * x * (x + 1) % MOD * Pow(2, MOD - 2) % MOD;
	}
	int pre[N];

	void solve() {
		for (int i = 1; i <= n; i++) {
			pre[i] = pre[i - 1] + w[i];
			if (pre[i] >= MOD) pre[i]-= MOD;
		}

		stack <array <int, 3>> st;
		int ans = 0, add = 0;

		for (int i = 1; i <= n; i++) {
			int H = h[i];
			(ans+= 1LL * SumnC2(H) * SumnC2(w[i]) % MOD) %= MOD;

			int L = i, R = i;

			while (!st.empty() && st.top()[0] >= h[i]) {
				int l = st.top()[1];
				int r = st.top()[2];
				L = min(L, l);
				add = (add - 1LL * (pre[r] - pre[l - 1] + MOD) % MOD * SumnC2(st.top()[0]) % MOD + MOD) % MOD; 
				st.pop();
			}
			
			
			(add+= 1LL * (pre[R - 1] - pre[L - 1] + MOD) % MOD * SumnC2(h[i]) % MOD) %= MOD;
			// cout << i << " " << add << '\n';
			(ans+= 1LL * w[i] * add % MOD) %= MOD;
			// cout << i << " " << w[i] * add << " " << add << "\n";
			(add+= 1LL * (pre[i] - pre[i - 1] + MOD) % MOD * SumnC2(h[i]) % MOD) %= MOD;

			st.push({h[i], L, R});
		}

		cout << ans % MOD;
	}	
}

int main () {
    ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    #define taskname "rect"
    if(fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
    }
    cin >> n;
    for (int i = 1; i <= n; i++) {
    	cin >> h[i];
    }
    for (int i = 1; i <= n; i++) {
    	cin >> w[i];
    }
    // return sub5 :: solve(), ko();
    return sub6 :: solve(), ko();
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fancyfence.cpp:91:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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