Submission #945670

#	Time	Username	Problem	Language	Result	Execution time	Memory
945670		yhkhoo	Fancy Fence (CEOI20_fancyfence)	C++17	25 / 100	36 ms	11160 KiB

fancyfence

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

#define int long long

typedef pair<int, int> pii;

const int MOD = 1000000007;

#define lsb(x) ((x) & (-x))

int n;
const int MAXN = 100005;
int fw[MAXN];

void update(int X, int V){
	X++;
	while(X<=n){
		fw[X] += V;
		X += lsb(X);
	}
}

int query(int R){
	R++;
	if(R==0) return 0;
	int result = 0;
	while(R){
		result += fw[R];
		R -= lsb(R);
	}
	return result;
}

inline int goat(int n, int m){
	if(n <= 0 || m <= 0) return 0;
	int x = (n%MOD)*((n+1)%MOD);
	x >>= 1;
	int y = (m%MOD)*((m+1)%MOD);
	y >>= 1;
	return (x*y)%MOD;
}

signed main(){
	cin.tie(0); ios_base::sync_with_stdio(0);
	cin >> n;
	vector<int> h(n), w(n), wp(n);
	vector<pii> hs;
	hs.reserve(n);
	for(int i=0; i<n; i++){
		cin >> h[i];
		hs.emplace_back(h[i], i);
	}
	for(int i=0; i<n; i++){
		cin >> w[i];
		if(i==0) wp[0] = w[0];
		else wp[i] = wp[i-1]+w[i];
	}
	sort(hs.begin(), hs.end());
	set<int> dead;
	dead.insert(-1);
	dead.insert(n);
	int ans=0;
	for(int i=0; i<n; i++){
		auto[ch, cs] = hs[i];
		int cph = query(cs);
		if(cph == ch){
			dead.insert(cs);
			continue;
		}
		auto pr = dead.upper_bound(cs);
		auto pl = pr;
		pl--;
		int cfr = (*pr)-1, cfl = (*pl)+1;
		int cfw = wp[cfr];
		if(cfl > 0) cfw -= wp[cfl-1];
		int uh = ch-cph;
		ans += goat(ch, cfw);
		ans -= goat(cph, cfw);
		update(cfl, uh);
		update(cfr+1, -uh);
		dead.insert(cs);
		ans += MOD;
		ans %= MOD;
	}
	cout << ans;
	return 0;
}

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