oj.uz

Submission #936616

# Submission time Handle Problem Language Result Execution time Memory
936616 2024-03-02T11:53:25 Z Batorgil952 Fancy Fence (CEOI20_fancyfence) C++14
12 / 100
 1 ms 4700 KB 
// **y ***** Khoroo
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair

using namespace std;

const ll N=1e5+5, mod=1e9+7;
ll h[N], w[N], tree[4*N], urt[4*N];
ll n;

void build(ll v, ll l, ll r){
	if(l==r) tree[v]=l, urt[v]=w[l];
	else{
		ll mid=(l+r)/2;
		build(2*v, l, mid);
		build(2*v+1, mid+1, r);
		if(h[tree[2*v]]<=h[tree[2*v+1]]){
			tree[v]=tree[2*v];
		}
		else{
			tree[v]=tree[2*v+1];
		}
		urt[v]=urt[2*v]+urt[2*v+1];
	}
}

ll query1(ll v, ll l, ll r, ll ql, ll qr){
	if(qr<l || r<ql) return -1;
	if(ql<=l && r<=qr) return tree[v];
	ll mid=(l+r)/2;
	ll x=query1(2*v, l, mid, ql, qr);
	ll y=query1(2*v+1, mid+1, r, ql, qr);
	if(x==-1) return y;
	if(y==-1) return x;
	if(h[x]<=h[y]) return x;
	return y;
 }

ll query2(ll v, ll l, ll r, ll ql, ll qr){
	if(qr<l || r<ql) return 0;
	if(ql<=l && r<=qr) return urt[v];
	ll mid=(l+r)/2;
	return query2(2*v, l, mid, ql, qr)+query2(2*v+1, mid+1, r, ql, qr);
}

ll Fun(ll l, ll r, ll tuvshin){
	if(l>r) return 0;
	ll p=query1(1, 1, n, l, r);
	ll q=query2(1, 1, n, l, r);
	ll a=h[p]-tuvshin;
	ll b=tuvshin;
	return ((((((q%mod)*(q+1))%mod)*500000004)%mod)*((((((2*b+a+1)%mod)*a)%mod)*500000004)%mod)%mod+Fun(l, p-1, h[p])+Fun(p+1, r, h[p]))%mod;
}

int main(){
	ll i;
	
	scanf("%lld",&n);
	
	for(i=1; i<=n; i++){
		scanf("%lld",&h[i]);
	}
	
	for(i=1; i<=n; i++){
		scanf("%lld",&w[i]);
	}
	
	build(1, 1, n);
	
	printf("%lld\n", Fun(1, n, 0));
	
	return 0;
}

Compilation message

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |  scanf("%lld",&n);
      |  ~~~~~^~~~~~~~~~~
fancyfence.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   scanf("%lld",&h[i]);
      |   ~~~~~^~~~~~~~~~~~~~
fancyfence.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%lld",&w[i]);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #3
0 / 13.0

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