oj.uz

Submission #949300

# Submission time Handle Problem Language Result Execution time Memory
949300 2024-03-19T05:22:11 Z Amaarsaa Fancy Fence (CEOI20_fancyfence) C++14
0 / 100
 1 ms 348 KB 
#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

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 / 0.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 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 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -