oj.uz

Submission #647027

# Submission time Handle Problem Language Result Execution time Memory
647027 2022-10-01T12:24:36 Z jamielim Fancy Fence (CEOI20_fancyfence) C++14
55 / 100
 32 ms 3520 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n;
int h[100005],w[100005];

inline ll choose2(ll x){
	return ((x)*(x-1)/2)%MOD;
}

int main(){
	//freopen("sample/input1.txt","r",stdin);
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d",&h[i]);
	for(int i=0;i<n;i++)scanf("%d",&w[i]);
	ll ans=0;
	vector<pair<ll,ll> > stk;
	stk.pb(0,0);
	ll cur=0;
	for(int i=0;i<n;i++){
		ll sum=0;
		while(stk.back().fi>h[i]){
			ii p=stk.back();stk.pop_back();
			cur-=((p.se%MOD)*choose2(p.fi+1))%MOD;
			cur%=MOD;
			sum+=p.se;
		}
		cur+=((sum%MOD)*choose2(h[i]+1))%MOD;
		cur%=MOD;cur+=MOD;cur%=MOD;
		
		ans+=(cur*(ll)(w[i]))%MOD; // left side is strictly from previous block, right side is (,] of current block
		ans%=MOD;
		//printf("a' %lld\n",ans);
		
		ans+=((choose2(h[i]+1)%MOD)*(choose2(w[i]+1)%MOD))%MOD; // left side is within current block
		ans%=MOD;
		//printf("a %lld\n",ans);
		
		cur+=((w[i]%MOD)*choose2(h[i]+1))%MOD;
		stk.pb(h[i],sum+w[i]);
	}
	printf("%lld",((ans%MOD)+MOD)%MOD);
}

Compilation message

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
fancyfence.cpp:29:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  for(int i=0;i<n;i++)scanf("%d",&h[i]);
      |                      ~~~~~^~~~~~~~~~~~
fancyfence.cpp:30:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |  for(int i=0;i<n;i++)scanf("%d",&w[i]);
      |                      ~~~~~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 11 ms 1512 KB Output is correct
4 Correct 21 ms 3504 KB Output is correct
5 Correct 22 ms 2400 KB Output is correct
6 Correct 19 ms 1620 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 3 ms 980 KB Output is correct
3 Correct 19 ms 2012 KB Output is correct
4 Correct 27 ms 3512 KB Output is correct
5 Correct 27 ms 3456 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 980 KB Output is correct
4 Correct 16 ms 2088 KB Output is correct
5 Correct 32 ms 3476 KB Output is correct
6 Correct 27 ms 3520 KB Output is correct
7 Correct 1 ms 328 KB Output is correct
8 Correct 3 ms 980 KB Output is correct
9 Correct 14 ms 2008 KB Output is correct
10 Correct 23 ms 3444 KB Output is correct
11 Correct 31 ms 3412 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #6
0 / 18.0

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