Submission #204161

#	Time	Username	Problem	Language	Result	Execution time	Memory
204161		mdn2002	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	0 / 100	1006 ms	5496 KiB

foehn_phenomena

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long n,q,s,t,ps[200005],a[200005],ans,sqt;
vector<pair<int,pair<int,int> > >v;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin>>n>>q>>s>>t;
    sqt=ceil(sqrt(q));
    long long b;
    cin>>b;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        long long aa=a[i];
        long long dif=b-aa;
        if(dif>=0)ans+=dif*t;
        else ans+=dif*s;
        b=aa;
    }
    int l,r;
    long long x,dif=0;
    while(q--)
    {
        cin>>l>>r>>x;

        long long la=a[l],ra=a[r],oa=a[l-1],va=a[r+1];
        for(int i=0;i<v.size();i++)
        {
            long long ll=v[i].first,rr=v[i].second.first,xx=v[i].second.second;
            if(ll<=l&&l<=rr)la+=xx;
            if(ll<=r&&r<=rr)ra+=xx;
            if(ll<=l-1&&l-1<=rr)oa+=xx;
            if(ll<=r+1&&r+1<=rr)va+=xx;
        }
        v.push_back({l,{r,x}});
        long long ll=la+x,rr=ra+x;
        if(l>0)
        {
            dif=oa-la;
            if(dif>=0)ans-=dif*t;
            else ans-=dif*s;
            dif=oa-ll;
            if(dif>=0)ans+=dif*t;
            else ans+=dif*s;
        }
        if(r<n)
        {
            dif=ra-va;
            if(dif>=0)ans-=dif*t;
            else ans-=dif*s;
            dif=rr-va;
            if(dif>=0)ans+=dif*t;
            else ans+=dif*s;
        }
        cout<<ans<<endl;
        if(v.size()<sqt)continue;
        for(int i=0;i<v.size();i++)
        {
            long long ll=v[i].first,rr=v[i].second.first,xx=v[i].second.second;
            ps[l]+=xx,ps[r+1]-=xx;
        }
        for(int i=1;i<=n;i++)
        {
            ps[i]+=ps[i-1];
            a[i]+=ps[i];
        }
        for(int i=1;i<=n;i++)ps[i]=0;
    }
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:33:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v.size();i++)
                     ~^~~~~~~~~
foehn_phenomena.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(v.size()<sqt)continue;
            ~~~~~~~~^~~~
foehn_phenomena.cpp:63:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v.size();i++)
                     ~^~~~~~~~~
foehn_phenomena.cpp:65:23: warning: unused variable 'll' [-Wunused-variable]
             long long ll=v[i].first,rr=v[i].second.first,xx=v[i].second.second;
                       ^~
foehn_phenomena.cpp:65:37: warning: unused variable 'rr' [-Wunused-variable]
             long long ll=v[i].first,rr=v[i].second.first,xx=v[i].second.second;
                                     ^~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 10
• Subtask 3: 0 / 60