Submission #204165

#	Time	Username	Problem	Language	Result	Execution time	Memory
204165		mdn2002	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	954 ms	13432 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);
    scanf("%lld",&n);
    scanf("%lld",&q);
    scanf("%lld",&s);
    scanf("%lld",&t);
    sqt=ceil(sqrt(q));
    long long b;
    scanf("%lld",&b);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        long long aa=a[i];
        long long dif=b-aa;
        if(dif>=0)ans+=dif*t;
        else ans+=dif*s;
        b=aa;
    }
    long long l,r,x,dif=0;
    while(q--)
    {
        scanf("%lld",&l);
        scanf("%lld",&r);
        scanf("%lld",&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;
        }
        printf("%lld\n",ans);
        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[ll]+=xx,ps[rr+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;
        v.clear();
    }
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:36:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v.size();i++)
                     ~^~~~~~~~~
foehn_phenomena.cpp:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(v.size()<sqt)continue;
            ~~~~~~~~^~~~
foehn_phenomena.cpp:66:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v.size();i++)
                     ~^~~~~~~~~
foehn_phenomena.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
foehn_phenomena.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&q);
     ~~~~~^~~~~~~~~~~
foehn_phenomena.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&s);
     ~~~~~^~~~~~~~~~~
foehn_phenomena.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&t);
     ~~~~~^~~~~~~~~~~
foehn_phenomena.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&b);
     ~~~~~^~~~~~~~~~~
foehn_phenomena.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&a[i]);
         ~~~~~^~~~~~~~~~~~~~
foehn_phenomena.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&l);
         ~~~~~^~~~~~~~~~~
foehn_phenomena.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&r);
         ~~~~~^~~~~~~~~~~
foehn_phenomena.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&x);
         ~~~~~^~~~~~~~~~~

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