Submission #949300

#	Time	Username	Problem	Language	Result	Execution time	Memory
949300		Amaarsaa	Fancy Fence (CEOI20_fancyfence)	C++14	0 / 100	1 ms	348 KiB

fancyfence

#include<bits/stdc++.h>
 
using namespace std;
using ll = long long ;
using pll = pair < ll, ll >;
 
struct Co {
	ll x, y, i;
};
ll ataman[100002], hemjee[100005];
bool cmp(Co& A, Co& B) {
	return A.y > B.y;
}
 
ll Get(ll x) {
	if ( x == ataman[x]) return x;
	return ataman[x] = Get(ataman[x]);
}
 
void Union(ll x, ll y) {
	x = Get(x);
	y = Get(y);
	if ( x == y) return;
	if ( x > y) swap(x, y);
	ataman[y] = x;
	hemjee[x] += hemjee[y];
	
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll t, n, m, ind, ans, z, s, sum, Mod, x, y, r, p, i, j, mod = 1e9 + 7;
	
	
	cin >> n;
	
	Mod = mod * 1e9;
	
	Co P[n + 2];
	
	for (i =1; i <= n; i ++) cin >> P[i].x;
	for (i =1; i <= n; i ++) cin >> P[i].y, P[i].i = i;
	
	sort ( P + 1,  P + n + 1, cmp);
	
	for (i = 1; i <= n; i ++) {
		ataman[i] = i;
	}
	ans = 0;
	sum = 0;
	P[n + 1].y = 0;
	for (i = 1; i <= n; i ++) {
		j = i;
		while ( P[i].y == P[j].y) {
			ind = P[i].i;
			x = ind;
			y = ind - 1;
			z = ind + 1;
			if ( hemjee[y] == 0 && hemjee[z] == 0) {
				hemjee[x] = P[i].x;
				sum = sum + ll(P[i].x*(P[i].x + 1)/2);
				sum %= mod;
			}
			else {
				if ( hemjee[y] == 0) {
					hemjee[x] = P[i].x;
					ataman[z] = x;
					hemjee[x] += hemjee[z];
					r = hemjee[z];
					r = r * (r + 1)/2;
					sum -= r;
					sum += Mod;
					sum %= mod;
					r = hemjee[x];
					r = r * (r + 1)/2;
					sum += r;
					sum %= mod;
				}
				else {
					if ( hemjee[z] == 0) {
						hemjee[x] = P[i].x;
						ataman[x] = y;
						r = hemjee[y];
						r =r * (r + 1)/2;
						sum -= r;
						sum += Mod;
						sum %= mod;
						hemjee[y] += hemjee[x];
						hemjee[y] %= mod;
						r = hemjee[y];
						r = r *( r + 1)/2;
						sum += r;
						sum%= mod;
					}
					else {
						hemjee[x] = P[i].x;
						ataman[x] = y;
						ataman[z] = y;
						r = hemjee[y];
						r = r * (r + 1)/2;
						sum -= r;
						sum += Mod;
						sum %= mod;
						r = hemjee[z];
						r = r * (r + 1)/2;
						sum -= r;
						sum += Mod;
						sum %= mod;
						hemjee[y] += hemjee[x];
						hemjee[y] += hemjee[z];
						hemjee[y] %= mod;
						r = hemjee[y];
						r = r * (r + 1)/2;
						sum += r;
						sum %= mod;
					}
				}
			}
			j ++;
		}
		i = j - 1;
		s = P[i].y * (P[i].y + 1)/2;
		p = P[i + 1].y * (P[i + 1].y + 1)/2;
//		cout << sum << " " << s - p << endl;
		r = sum * (s - p);
		ans += r;
		ans %= mod;
	}
	cout << ans << endl;
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:33:5: warning: unused variable 't' [-Wunused-variable]
   33 |  ll t, n, m, ind, ans, z, s, sum, Mod, x, y, r, p, i, j, mod = 1e9 + 7;
      |     ^
fancyfence.cpp:33:11: warning: unused variable 'm' [-Wunused-variable]
   33 |  ll t, n, m, ind, ans, z, s, sum, Mod, x, y, r, p, i, j, mod = 1e9 + 7;
      |           ^

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