Submission #458599

#	Time	Username	Problem	Language	Result	Execution time	Memory
458599		AriaH	Fancy Fence (CEOI20_fancyfence)	C++11	100 / 100	149 ms	32124 KiB

fancyfence

/** work as hard as you can and keep the first place **/

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>

using namespace std;

typedef long long			ll;
typedef long double			ld;
typedef pair < int, int > 	pii;
typedef pair < ll, ll > 	pll;

#define F					first
#define S					second
#define all(x)				x.begin(), x.end()
#define SZ(x)				(int)x.size()
#define Mp					make_pair

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const int LOG = 20;

ll pw(ll a, ll b, ll M = mod, ll ret = 1) { while(b) { ret = ret * (b & 1? a : 1) % M, a = a * a % M, b >>= 1; } return ret; }

ll inv2, ps[N];

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

vector < int > cm, Q[N];

set < pair < pii, ll > > st;

ll C2(ll x)
{
	x %= mod;
	return x * (x - 1) % mod * inv2 % mod;
}

ll baze(int l, int r)
{
	return 1ll * (r + l) * (r - l + 1) % mod * inv2 % mod;
}

void add(int l, int r)
{
	if(l > r) return;
	st.insert(Mp(Mp(l, r), ps[r] - ps[l - 1]));
}

int main()
{
	inv2 = pw(2, mod - 2, mod);
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d", &h[i]);
		cm.push_back(h[i]);
	}
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d", &w[i]);
		ps[i] = ps[i - 1] + w[i];
	}
	st.insert(Mp(Mp(1, n), ps[n]));
	cm.push_back(0);
	sort(all(cm));
	cm.resize(unique(all(cm)) - cm.begin());
	for(int i = 1; i <= n; i ++)
	{
		int cu = lower_bound(all(cm), h[i]) - cm.begin();
		Q[cu].push_back(i);
	}
	ll sum = C2(ps[n] + 1), tot = 0;
	for(int i = 1; i < SZ(cm); i ++)
	{
		for(auto id : Q[i - 1])
		{
			auto it = st.lower_bound(Mp(Mp(id, 1e9), -1));
			it --;
			int l = (*it).F.F, r = (*it).F.S;
			sum = (sum - C2(ps[r] - ps[l - 1] + 1) + mod) % mod;
			st.erase(it);
			add(l, id - 1), add(id + 1, r);
			sum = (sum + C2(ps[r] - ps[id] + 1) + C2(ps[id - 1] - ps[l - 1] + 1)) % mod;
		}
		///printf("i = %d cm = %d sum = %lld\n", i, cm[i], sum);
		tot = (tot + baze(cm[i - 1] + 1, cm[i]) * sum % mod) % mod;
	}
	printf("%lld", tot);
	return 0;
}
/** test corner cases(n = 1?) watch for overflow or minus indices **/

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
fancyfence.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%d", &h[i]);
      |   ~~~~~^~~~~~~~~~~~~
fancyfence.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d", &w[i]);
      |   ~~~~~^~~~~~~~~~~~~

• 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