oj.uz

Submission #960016

# Submission time Handle Problem Language Result Execution time Memory
960016 2024-04-09T13:35:02 Z Huseyn123 Fancy Fence (CEOI20_fancyfence) C++17
12 / 100
 2 ms 2492 KB 
#include <bits/stdc++.h> 
#define MAX 100001
#define MOD 1000000007
using namespace std; 
typedef long long ll;
ll n,x,y,z,w[MAX],h[MAX],a[MAX];
struct DSU{
	vector<int> e;
	DSU(int N){e.resize(N+1,-1);}
	int get(int x){return (e[x]<0) ? x : e[x]=get(e[x]);}
	int size(int x){return w[get(x)];}
	bool unite(int x,int y){
		x=get(x);
		y=get(y);
		if(x==y) return false; 
		if(e[x]>e[y]) swap(x,y);
		e[x]+=e[y]; w[x]+=w[y]; e[y]=x;
		return true;
	}
};
ll powmod(ll x,ll y,ll mod){
	if(y==0){
		return 1;
	}
	ll res=1;
	x%=mod;
	while(y>0){
		if(y%2){
			res*=x;
			res%=mod;
		}
		y/=2;
		x*=x;
		x%=mod;
	}
	return res;
}
ll inv(ll n,ll mod){
	return powmod(n,mod-2,mod);
}
ll mul(ll x,ll y){
	return (x*y)%MOD;
}
ll f(ll W,ll H){
	ll res=1;
	res=mul(res,W);
	res=mul(res,W+1);
	res=mul(res,H);
	res=mul(res,H+1);
	res=mul(res,z);
	return res;
}
void solve(){
	cin >> n; 
	z=inv(4,MOD);
	for(int i=0;i<n;i++){
		cin >> h[i];
	}
	for(int i=0;i<n;i++){
		cin >> w[i];
	}
	vector<array<ll,3>> c;
	for(int i=0;i<n;i++){
		c.push_back({h[i],w[i],(ll)i});
	}
	sort(c.rbegin(),c.rend());
	ll res=0;
	DSU dsu(n);
	for(auto x:c){
		ll cnt=x[1];
		a[x[2]]=1;
		if(x[2]-1>=0 && a[x[2]-1]){
			y=dsu.size(x[2]-1);
			res-=f(y,x[0]);
			res=(res+MOD)%MOD;
			cnt+=y;
			dsu.unite(x[2],x[2]-1);
		}
		if(x[2]+1<n && a[x[2]+1]){
			y=dsu.size(x[2]+1);
			res-=f(y,x[0]);
			res=(res+MOD)%MOD;
			cnt+=y;
			dsu.unite(x[2],x[2]+1);
		}
		res+=f(cnt,x[0]);
		//cout << cnt << " " << x[0] << " " << res << "\n";
		res%=MOD;
	}
	cout << res << "\n";
}
int main(){
	//freopen("input0.txt","r",stdin);
	solve();
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2492 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 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct

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 2392 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 2 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 2396 KB Output is correct
2 Incorrect 1 ms 2492 KB Output isn't correct
3 Halted 0 ms 0 KB -