Submission #545526

#	Time	Username	Problem	Language	Result	Execution time	Memory
545526		leaked	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	36 ms	5688 KiB

fancyfence

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_resp ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<int,ll> pil;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const ll inf=1e18;
const int M=1e9+7;
void add(int &a,int b){
    a+=b;
    if(a>=M) a-=M;
    else if(a<0) a+=M;
}
int mult(int a,int b){
    return 1ll*a*b%M;
}
int binpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=mult(ans,a);
        a=mult(a,a);b>>=1;
    }
    return ans;
}
signed main(){
    fast_resp;
    int n;
    cin>>n;
    vec<int>a(n),b(n);
    vec<array<int,4>> arr;
    /// h,sum_prefs,sum_prefs^1,cnt
    vec<int>pref(n);
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
//    for(int i=0;i<n;i++){
//        cin>>a[i]>>b[i];
//        pref[i]=(i?pref[i-1]:0);
//        add(pref[i],b[i]);
//    }
    arr.pb({(int)-1e9-1,0,0,0});
    int ans=0;
//    int sumwh=0;
//    int sumh=0;
    int their=0;
    int p2=binpow(2,M-2);
    for(int i=0;i<n;i++){
        array<int,4> me={0,0,0,0};
        me[0]=a[i];
//        me[1]=b[i];me[2]=1;
        while(sz(arr) && arr.back()[0]>=a[i]){
            int h=arr.back()[0];
            int smw2=arr.back()[1];
            int cnt=arr.back()[2];

            add(their,-mult(smw2,mult(h,h+1)));
            arr.pop_back();

            add(me[1],smw2);
            add(me[2],cnt);
//            add(me[2],cnt);
        }

        int h=me[0];
        int smw2=me[1];
        int cnt=me[2];

        add(their,mult(smw2,mult(h,h+1)));

        add(ans,mult(b[i],their));
        add(ans,mult(p2,mult(b[i],mult(a[i],mult(b[i]+1,a[i]+1)))));

        add(me[1],b[i]);add(me[2],1);
        add(their,mult(b[i],mult(h,h+1)));
        arr.pb(me);
//        add(ans,mult(b[i],mult(h,h+1)));

//        add(ans,mult(sumh,mult(pref[i],pref[i])));
//        add(ans,mult(2,mult(sumwh,pref[i])));
    }
//    cout<<ans<<endl;
    ans=mult(ans,binpow(2,M-2));
    cout<<ans;
    return 0;
}
/*

*/

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:78:13: warning: unused variable 'cnt' [-Wunused-variable]
   78 |         int cnt=me[2];
      |             ^~~

• 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