oj.uz

Submission #961804

# Submission time Handle Problem Language Result Execution time Memory
961804 2024-04-12T13:26:12 Z starchan Fancy Fence (CEOI20_fancyfence) C++17
55 / 100
 28 ms 8256 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int mod = 1e9+7;
const int MX = 1e5+5;

int c2(int x)
{
	return ((x*(x+1))/2)%mod;
}

int sum;
vector<int> pa(MX, -1);
vector<int> dp(MX, 0);

int leader(int u)
{
	if(pa[u] < 0)
		return u;
	else
		return pa[u] = leader(pa[u]);
}

void merge(int u, int v)
{
	u = leader(u); v = leader(v);
	if(u==v)
		return;
	if(pa[u] < pa[v])
		swap(u, v);
	pa[v]+=pa[u];
	sum+=(dp[u]*dp[v]); sum%=mod;
	dp[v]+=dp[u]; dp[v]%=mod;
	pa[u] = v;
	return;
}
signed main()
{
	fast();
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> b(n);
	vector<in> ab(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
		ab[i][0] = a[i];
	}
	for(int i = 0; i < n; i++)
	{
		cin >> b[i];
		ab[i][1] = i;
	}
	sort(ab.rbegin(), ab.rend());
	vector<int> C{ab[0][0]};
	for(auto p: ab)
	{
		if(C.back() != p[0])
			C.pb(p[0]);
	}
	int ans = 0;
	int l = 0; int D = C.size(); C.pb(0);
	for(int i = 0; i < D; i++)
	{
		int L = l;
		while((l < n) && (ab[l][0] >= C[i]))
		{
			int lp = ab[l][1];
			dp[lp] = b[lp];
			sum+=c2(b[lp]);
			sum%=mod;
			l++;
		}
		l = L;
		while((l < n) && (ab[l][0] >= C[i]))
		{
			int lp = ab[l][1];
			if(((lp+1) < n) && (a[lp+1] >= C[i]))
				merge(lp, lp+1);
			if(((lp-1) >= 0) && (a[lp-1] >= C[i]))
				merge(lp, lp-1);
			l++;
		}
		int val = (sum*((c2(C[i])-c2(C[i+1]))%mod))%mod;
		ans+=val; ans%=mod;
	}
	cout << ans << "\n";
	return 0;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Incorrect 1 ms 1884 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 1 ms 1880 KB Output is correct
4 Correct 1 ms 1880 KB Output is correct
5 Correct 1 ms 1884 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 13 ms 4196 KB Output is correct
4 Correct 23 ms 6232 KB Output is correct
5 Correct 23 ms 6312 KB Output is correct
6 Correct 22 ms 6232 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 3 ms 2552 KB Output is correct
3 Correct 12 ms 4360 KB Output is correct
4 Correct 22 ms 7004 KB Output is correct
5 Correct 23 ms 6996 KB Output is correct
6 Correct 1 ms 2136 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 12 ms 4444 KB Output is correct
5 Correct 28 ms 7072 KB Output is correct
6 Correct 24 ms 7084 KB Output is correct
7 Correct 2 ms 1880 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Correct 12 ms 4960 KB Output is correct
10 Correct 21 ms 8156 KB Output is correct
11 Correct 24 ms 8256 KB Output is correct
12 Correct 1 ms 1884 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Incorrect 1 ms 1884 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Incorrect 1 ms 1884 KB Output isn't correct
3 Halted 0 ms 0 KB -