제출 #1216402

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1216402		thdh__	Fancy Fence (CEOI20_fancyfence)	C++20	12 / 100	1 ms	528 KiB

fancyfence

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fu(x,a,b) for (auto x=a;x<=b;x++)
#define fd(x,a,b) for (auto x=a;x>=b;x--)
#define int ll

using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

/*
Competitive Programming notes that I need to study & fix my dumbass self:

1. Coding:
- Always be sure to check the memory of arrays (maybe use vectors), for loops, I don't know
- Always try to maximize the memory if possible, even if you are going for subtasks
- Do not exploit #define int long long, it will kill you

2. Stress:
- Don't be cocky and think stressing with your dumbass brute-force solution will give you guaranteed AC. 
- Always try generating big testcases and try if they run

3. Time management:
- Don't overcommit or undercommit, always spend a certain amount of time to think a problem, don't just look at it and say I'm fucked
- Do not spend too much time coding brute-force solutions, they should be easily-codable solutions that don't take up too much time

I hate offline because I am dumb
*/

typedef pair<int, int> ii;
const int N = 2e5+5;
const int mod = 1e9+7;
const int inf = 1e18;
using cd = complex<double>;
const long double PI = acos(-1);
int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} 

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

int calc(int x, int y) 
{
	return ((x * (x+1) / 2ll) % mod) * ((y * (y+1) / 2ll) % mod) % mod;
}

void solve()
{
	cin>>n;
	for (int i = 1; i <= n; i++) cin>>h[i];
	for (int i = 1; i <= n; i++) cin>>w[i], pref[i] = pref[i-1] + w[i];
	stack<int> st;
	st.push(0);
	int ans = 0;
	for (int i = 1; i <= n+1; i++) 
	{
		while (!st.empty() && h[i] <= h[st.top()]) 
		{
			int pos = st.top();
			st.pop();
			if (st.empty()) break;
			int x = h[pos] - max(h[i], h[st.top()]), y = pref[i-1] - pref[st.top()];
			int add = (calc(x,y) + (x * max(h[i], h[st.top()]) % mod) * (y * (y+1) / 2ll % mod) % mod) % mod;
			ans = (ans + add) % mod;
		}
		st.push(i);
	}
	cout<<ans;
}

/*
Go through the mistakes you usually make and revise your code, for god's sake...
*/

signed main()
{
	bruh
	//freopen("input.inp","r",stdin);
	//freopen("output.inp","w",stdout);
	int t = 1;
	// cin>>t;
	while (t--)
	{
		solve();
		cout<<"\n";
	}
}

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