Submission #320419

#	Time	Username	Problem	Language	Result	Execution time	Memory
320419		tasfiq4	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	34 ms	7148 KiB

fancyfence

/// #
#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<lld,lld > pii;
#define pi acos(-1)
#define fr(i,m,n) for(i=m;i<n;i++)
#define fu(i,m,n) for(i=m;i>=n;i--)
#define vec vector<lld>
#define pb push_back
#define pp pop_back()
#define ft first
#define sd second
#define all(v) v.begin(),v.end()
#define mom(ara) memset(ara,0,sizeof(ara));
#define m1m(ara) memset(ara,-1,sizeof(ara));
#define endl "\n"
#define eps 1.19209e-07
const lld mod=1e9+7;
lld pref[100010],suf[100010];
lld cal(lld x,lld y)
{
	x%=mod;y%=mod;
	lld i=(x*(x+1))/2,j=(y*(y+1))/2;
	i%=mod;j%=mod;
	return (i*j)%mod;
}
int main()
{ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    lld i,j,k,a,b,c,x,y,z,n,m,ans,t;

    cin>>n;
    vec h,w;
    fr(i,0,n)
    {
    	cin>>x;
    	h.pb(x);
    }
    fr(i,0,n)
    {
    	cin>>x;
    	w.pb(x);
    }
    stack<pii> st;
    fr(i,0,n)
    {
    	if(st.empty() || st.top().ft<h[i])
    	{
    		st.push({h[i],w[i]});
    		pref[i]=0;
    	}
    	else
    	{
    		x=0;
    		while(!st.empty() && st.top().ft>=h[i])
    		{
    			x+=st.top().sd;
    			st.pop();
    		}
    		pref[i]=x;
    		st.push({h[i],x+w[i]});
    	}
    }
    while(!st.empty()) st.pop();
    fu(i,n-1,0)
    {
    	if(st.empty() || st.top().ft<=h[i])
    	{
    		st.push({h[i],w[i]});
    		suf[i]=0;
    	}
    	else
    	{
    		x=0;
    		while(!st.empty() && st.top().ft>h[i])
    		{
    			x+=st.top().sd;
    			st.pop();
    		}
    		suf[i]=x;
    		st.push({h[i],x+w[i]});
    	}
    }
    ans=0;
    fr(i,0,n)
    {
    	ans+=cal(h[i],pref[i]+w[i]+suf[i]);
    	ans%=mod;
    	ans-=(cal(pref[i],h[i])+cal(suf[i],h[i]))%mod;
    	ans+=mod;
    	ans%=mod;
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:30:11: warning: unused variable 'j' [-Wunused-variable]
   30 |     lld i,j,k,a,b,c,x,y,z,n,m,ans,t;
      |           ^
fancyfence.cpp:30:13: warning: unused variable 'k' [-Wunused-variable]
   30 |     lld i,j,k,a,b,c,x,y,z,n,m,ans,t;
      |             ^
fancyfence.cpp:30:15: warning: unused variable 'a' [-Wunused-variable]
   30 |     lld i,j,k,a,b,c,x,y,z,n,m,ans,t;
      |               ^
fancyfence.cpp:30:17: warning: unused variable 'b' [-Wunused-variable]
   30 |     lld i,j,k,a,b,c,x,y,z,n,m,ans,t;
      |                 ^
fancyfence.cpp:30:19: warning: unused variable 'c' [-Wunused-variable]
   30 |     lld i,j,k,a,b,c,x,y,z,n,m,ans,t;
      |                   ^
fancyfence.cpp:30:23: warning: unused variable 'y' [-Wunused-variable]
   30 |     lld i,j,k,a,b,c,x,y,z,n,m,ans,t;
      |                       ^
fancyfence.cpp:30:25: warning: unused variable 'z' [-Wunused-variable]
   30 |     lld i,j,k,a,b,c,x,y,z,n,m,ans,t;
      |                         ^
fancyfence.cpp:30:29: warning: unused variable 'm' [-Wunused-variable]
   30 |     lld i,j,k,a,b,c,x,y,z,n,m,ans,t;
      |                             ^
fancyfence.cpp:30:35: warning: unused variable 't' [-Wunused-variable]
   30 |     lld i,j,k,a,b,c,x,y,z,n,m,ans,t;
      |                                   ^

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