제출 #1342390

#제출 시각아이디문제언어결과실행 시간메모리
1342390blackscreen1Fancy Fence (CEOI20_fancyfence)C++20
0 / 100
1 ms344 KiB
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, cans = 0, cc = 0, nx;
pair<pll, ll> a[100005];
bool act[100005];
ll par[100005], sz[100005], ts[100005];
ll find(ll x) {
	return (par[x] == x ? x : par[x] = find(par[x]));
}
void merge(ll x, ll y) {
	x = find(x), y = find(y);
	if (sz[x] < sz[y]) swap(x, y);
	sz[x] += sz[y];
	cc += ts[x]*ts[y];
	cc %= MOD1;
	ts[x] += ts[y];
	par[y] = x;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	iloop(0, n) cin >> a[i].first.first;
	iloop(0, n) cin >> a[i].first.second;
	iloop(0, n) {
		a[i].second = i;
		sz[i] = 1;
		par[i] = i;
	}
	sort(a, a+n);
	iloop(n-1, -1) {
		nx = (i ? a[i-1].first.first : 0);
		act[a[i].second] = 1;
		ts[a[i].second] = a[i].first.second;
		cc += a[i].first.second*(a[i].first.second+1)/2;
		cc %= MOD1;
		if (a[i].second && act[a[i].second-1]) merge(a[i].second, a[i].second-1);
		if (a[i].second < n-1 && act[a[i].second+1]) merge(a[i].second, a[i].second+1);
		cans += (a[i].first.first - nx)*cc*(nx+1);
		cans %= MOD1;
		//cout << cans << "\n";
	}
	cout << cans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...