Submission #639818

#	Time	Username	Problem	Language	Result	Execution time	Memory
639818		hail	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	81 ms	10112 KiB

fancyfence

#include <bits/stdc++.h>
 
using namespace std;
 
#define vi vector<int>
#define vll vector<long long>
#define pb push_back
using ll= long long;
#define fast_io ios::sync_with_stdio(0); cin.tie(0)
#define inpint(x) int x; cin>>x
#define inpll(x) long long x; cin>>x
#define fl(i, n) for(int i=0; i<n; i++)
#define flo(i, n) for(int i=1; i<=n; i++)
#define int long long 
#define pi pair<int, int>
#define mp make_pair
#define ld long double

const int MOD = 998244353;
const int MODa = 7 + (int)1e9;
const int INF = 1 + (int)1e18;

const int MODinv2 = 500000004;

int nc2(int i)
{
	int ans = 0;
	i %= MODa;
	ans = i*(i-1);
	ans %= MODa;
	ans *= MODinv2;
	ans %= MODa;

	return ans;
}

int calc(int h, int w)
{
	h %= MODa;
	w %= MODa;
	int ne = (h+1)*(w+1);
	ne %= MODa;

	int ans = nc2(ne);
	int hr = nc2(h+1);
	int wr = nc2(w+1);

	hr *= (w+1);
	hr %= MODa;

	wr *= (h+1);
	wr %= MODa;

	ans -= hr;
	ans += MODa;
	ans %= MODa;

	ans -= wr;
	ans += MODa;
	ans %= MODa;

	ans *= MODinv2;
	ans %= MODa;

	return ans;
}

vector<int> h(0);
vector<int> w(0); 
vector<int> wp(0);

bool rsort(int x, int y)
{
	if(h[x]==h[y]) return x<y;
	return h[x]<h[y];
}

void solve()
{
	int n;
	cin>>n;

	h.resize(n+2);
	w.resize(n+2);
	wp.resize(n+2);
	wp[0] = 0;
	h[0] = 0;
	h[n+1] = 0;
	w[n+1] = 0;

	int ans = 0;

	for(int i=1; i<=n; i++)
	{
		cin>>h[i];
	}

	for(int i=1; i<=n; i++)
	{
		cin>>w[i];
		wp[i] = wp[i-1] + w[i];
	}

	vector<int> rec(n+1, 0);
	iota(rec.begin(), rec.end(), 0);

	set<int> done;

	sort(rec.begin()+1, rec.end(), rsort);

	for(int i=1; i<=n; i++)
	{
		auto it = done.lower_bound(rec[i]);
		int l, r;
		if(it==done.end())
		{
			r = n;
		}
		else
		{
			r = (*it)-1;
		}

		if(it == done.begin())
		{
			l = 1;
		}
		else
		{
			it--;
			l = (*it)+1;
		}

		int wis = wp[r] - wp[l-1];
		wis %= MODa;

		int hd = max(h[l-1], h[r+1]);

		if(hd==h[rec[i]])
		{
			done.insert(rec[i]);
			continue;
		}

		ans += calc(h[rec[i]], wis);
		ans %= MODa;

		ans -= calc(hd, wis);
		ans += MODa;	
		ans %= MODa;

		done.insert(rec[i]);	
	}

	cout<<ans;
}

int32_t main()
{
    fast_io;
 
    int t=1; 
    //cin>>t;
    while(t--)
    {
        solve();
    }
    cout<<endl;
}

• 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