oj.uz

Submission #943108

# Submission time Handle Problem Language Result Execution time Memory
943108 2024-03-11T08:21:53 Z shoryu386 Fancy Fence (CEOI20_fancyfence) C++17
0 / 100
 2 ms 2396 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define MAX 100007
#define MOD 1000000007

tuple<int, int, int> hw[MAX];
int p[MAX];
int sumsz[MAX];

int storeSqrSum = 0;

int compute(int x){
	return ( (x * (x+1))/2 ) %MOD;
}

void activate(int a){
	sumsz[a] = get<1>(hw[a]);
	storeSqrSum += compute(get<1>(hw[a]));
	storeSqrSum %= MOD;
}

int root(int a){
	if (a == p[a]) return a;
	return p[a] = root(p[a]);
}

void merge(int a, int b){
	a = root(a); b = root(b);
	if (a == b) return;
	
	p[a] = b;
	
	storeSqrSum -= compute(sumsz[a]);
	storeSqrSum += MOD; storeSqrSum %= MOD;
	
	storeSqrSum -= compute(sumsz[b]);
	storeSqrSum += MOD; storeSqrSum %= MOD;
	
	sumsz[b] += sumsz[a];
	storeSqrSum += compute(sumsz[b]);
	storeSqrSum %= MOD;
}

main(){
	int n; cin >> n;
	
	
	
	set<int> heights;
	
	for (int x = 0; x < n; x++) cin >> get<0>(hw[x]), heights.insert(get<0>(hw[x]));
	for (int x = 0; x < n; x++) cin >> get<1>(hw[x]), get<2>(hw[x]) = x;
	
	sort(hw, hw+n);
	reverse(hw, hw+n);
	for (int x = 0; x < n; x++) p[x] = x, sumsz[x] = 0;
	
	int ptr = 0;
	
	int ans = 0;
	
	for (int curh = 100; curh >= 1; curh--){
		while (ptr != n && get<0>(hw[ptr]) == curh){
			activate(ptr);
			
			if (ptr != 0 && sumsz[ptr-1] != 0) merge(ptr, ptr-1);
			if (ptr != n-1 && sumsz[ptr+1] != 0) merge(ptr, ptr+1);
			
			ptr++;
		}
		
		int heightSqr = curh;
		ans += (storeSqrSum * heightSqr)%MOD;
		
		ans %= MOD;
		
		//cerr << curh << ' ' << storeSqrSum << ' ' << (storeSqrSum * heightSqr)%MOD << '\n';
		
	}
	
	cout << ans;
	
	
	
}

Compilation message

fancyfence.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main(){
      | ^~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #6
0 / 18.0

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