Submission #943130

#	Time	Username	Problem	Language	Result	Execution time	Memory
943130		shoryu386	Fancy Fence (CEOI20_fancyfence)	C++17	12 / 100	1 ms	2652 KiB

fancyfence

#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]; //sumsz[b] %= MOD; //????????????????????
	storeSqrSum += compute(sumsz[b]);
	storeSqrSum %= MOD;
}

int rainbow(int start, int end){
	if ( (end-start)%2 ){
		//nice, no mid element
		int res = start+end;
		
		return (res * ((end-start+1)/2))%MOD;
	}
	else{
		int res = start+end;
		
		return ((res * ((end-start+1)/2))%MOD + (start+end)/2)%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;
	
	heights.insert(0);
	for (auto it = heights.rbegin(); it != heights.rend(); it++){
		if (*it == 0) break;
		
		while (ptr != n && get<0>(hw[ptr]) == *it){
			
			int idx = get<2>(hw[ptr]);
			
			activate( idx );
			
			if (idx != 0 && sumsz[idx-1] != 0) merge(idx, idx-1);
			if (idx != n-1 && sumsz[idx+1] != 0) merge(idx, idx+1);
			
			ptr++;
		}
		
		int curh = *it, nexth = (*next(it));
		ans += (storeSqrSum * rainbow(nexth+1, curh))%MOD;
		
		ans %= MOD;
		
		//cerr << curh << ' ' << nexth << ' ' << storeSqrSum << ' ' << (storeSqrSum * rainbow(nexth+1, curh))%MOD << '\n';
		
	}
	
	cout << ans;
	
	
	
}

Compilation message (stderr)

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

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