oj.uz

Submission #697046

# Submission time Handle Problem Language Result Execution time Memory
697046 2023-02-08T03:32:46 Z vjudge1 Fancy Fence (CEOI20_fancyfence) C++17
12 / 100
 1 ms 420 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
const int mod=1e9+7, maxn=1e6+5;
ll n, h[maxn], lebar[maxn], par[maxn], sz[maxn], kiri, kanan, w, t, ans, last, v[maxn];
bool vis[maxn];

int find(int x) {
	if(par[x]==x) return x;
	return par[x]=find(par[x]);
}

void join(int u, int v) {
	int ou=find(u), ov=find(v);
	if(ou!=ov) {
		assert(ov<ou);
		par[ou]=ov;
		sz[ov]+=sz[ou];
		lebar[ov]+=lebar[ou];
	}
}

ll deret(ll a, ll b) {
	assert(a<=b);
	return ((b-a+1)*(a+b)/2)%mod;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for(int i=1; i<=n; i++) {
		cin >> h[i];
		v[i]=par[i]=i;
		sz[i]=1;
	}
	for(int i=1; i<=n; i++) cin >> lebar[i];
	sort(v+1, v+n+1, [](auto ki, auto ka) {
		return h[ki]>h[ka];
	});
	last=1;
	for(int i=1; i<=n; i++) {
		if(i==n||h[v[i]]>h[v[i+1]]) {
			for(int j=last; j<=i; j++) {
				if(h[v[j]]<=h[v[j]-1]) join(v[j], v[j]-1);
				if(h[v[j]]<=h[v[j]+1]) join(v[j]+1, v[j]);
			}
			for(int j=last; j<=i; j++) {
				kiri=find(v[j]);
				if(vis[kiri]) continue;
				kanan=kiri+sz[kiri]-1, w=lebar[kiri], t=h[v[j]];
				// cout << v[j] << ' ' << t << ' ' << w << '\n';
				ans=(((deret(max(h[kiri-1], h[kanan+1])+1, t)*deret(1, w))%mod)+ans)%mod;
				vis[kiri]=true;
			}
			for(int j=last; j<=i; j++) vis[find(v[j])]=false;
			last=i+1;
		}
	}
	cout << ans << '\n';
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 336 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 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #5
0 / 15.0

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

Subtask #7
0 / 27.0

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