Submission #572664

#	Time	Username	Problem	Language	Result	Execution time	Memory
572664		jiahng	Fancy Fence (CEOI20_fancyfence)	C++14	12 / 100	2 ms	388 KiB

fancyfence

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

typedef long long ll;
//~ #define ll int
#define ll int
typedef pair<int32_t, int32_t> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 200001
#define INF 1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;

int N,H[maxn],W[maxn],ss[maxn],ss2[maxn];
int32_t main(){
    fast;
    cin >> N;
    FOR(i,1,N) cin >> H[i];
    FOR(i,1,N) cin >> W[i];
    FOR(i,1,N){
		ss[i] = (ss[i-1] + W[i]) % MOD;
		ss2[i] = (ss2[i-1] + (W[i] * W[i]) % MOD) % MOD;
	}
    
    set <int> st;
    vi v(N); iota(all(v), 1);
    sort(all(v), [](int i,int j){
		return H[i] < H[j];
	});
	int ans = 0;
	st.insert(N+1); st.insert(0);
	aFOR(i,v){
		int l = *(--st.lower_bound(i)) + 1;
		int r = *st.upper_bound(i) - 1;
		
		int res = 0;
		(res += ((ss[r] - ss[l-1]) * (ss[r] - ss[l-1])) % MOD) %= MOD;
		(res -= (ss2[r] - ss2[l-1]) % MOD) %= MOD;
		
		(res -= ((ss[r] - ss[i]) * (ss[r] - ss[i])) % MOD) %= MOD;
		(res += (ss2[r] - ss2[i]) % MOD) %= MOD;
		
		(res -= ((ss[i-1] - ss[l-1]) * (ss[i-1] - ss[l-1])) % MOD) %= MOD;
		(res += (ss2[i-1] - ss2[l-1]) % MOD) %= MOD;
		res /= 2;
		//~ (res -= (W[i] * W[i]) % MOD) %= MOD;
		int hc2 = (H[i] * (H[i] + 1) / 2) % MOD;
		(ans += (res * hc2) % MOD) %= MOD;
		//~ cout << ans << '\n';
		st.insert(i);
	}    
	
	FOR(i,1,N){
		(ans += ((((W[i] * (W[i]+1)) / 2) % MOD)
			* (((H[i] * (H[i]+1)) / 2) % MOD)) % MOD) %= MOD;
	}
	if (ans < 0) ans += MOD;
	cout << ans;
}

• 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