Submission #57884

#	Time	Username	Problem	Language	Result	Execution time	Memory
57884		jorik	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	313 ms	26336 KiB

foehn_phenomena

#include <bits/stdc++.h>

using namespace std;

//int dirs[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
//int dirs[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

vector<long long> ft;

void single_update(int start, long long val)
{
    for(int i=start; i<ft.size(); i+=i&(-i))
    {
        ft[i]+=val;
    }
}

void update(int from, int to, long long val)
{
    single_update(from,val);
    single_update(to+1,-val);
}

long long get_val(int start)
{
    long long ret=0;
    for(int i=start; i>0; i-=i&(-i)) ret += ft[i];
    return ret;
}

long long s, t;

long long trans(long long val1, long long val2)
{
    if(val2>val1) return -abs(val1-val2)*s;
    return abs(val1-val2)*t;
}

int main()
{
    //freopen("inp.in", "r", stdin);
    //freopen("outp.out", "w", stdout);
    //ios::sync_with_stdio(false);
    int n, q;
    scanf("%d %d %lld %lld", &n, &q, &s, &t);
    n=n+1;
    vector<long long> heights(n);
    for(int i=0; i<n; i++) scanf("%lld", &heights[i]);
    ft.assign(n+1,0);
    for(int i=1; i<=n; i++) update(i,i,heights[i-1]);
    /*for(int i=1; i<=n; i++)
    {
        cerr << "ft[" << i << "]: " << ft[i] << endl;
    }*/
    long long ans=0;
    for(int i=1; i<n; i++)
    {
        ans += trans(heights[i-1],heights[i]);
    }
    //cerr << "ans: " << ans << endl;
    for(int query_no=1; query_no<=q; query_no++)
    {
        int from, to;
        long long by;
        scanf("%d %d %lld", &from, &to, &by);
        //from--;
        //to--;
        if(from-1>=0) ans -= trans(get_val(from), get_val(from+1));
        //if(query_no==1) cerr << "hier1: " << ans << endl;
        if(to+1<n) ans -= trans(get_val(to+1),get_val(to+2));
        //if(query_no==1) cerr << "hier2: " << ans << endl;
        //cerr << get_val(2) << " " << get_val(3) << endl;
        //cerr << from+1 << " " << to+1 << endl;
        update(from+1,to+1,by);
        /*for(int i=1; i<=n; i++)
        {
            cerr << "ft[" << i << "]: " << ft[i] << endl;
        }*/
        //cerr << get_val(2) << " " << get_val(3) << endl;
        if(from-1>=0) ans += trans(get_val(from), get_val(from+1));
        //if(query_no==1) cerr << "hier3: " << ans << endl;
        //cerr << to+1 << " " << to+2 << endl;
        if(to+1<n) ans += trans(get_val(to+1),get_val(to+2));
        //if(query_no==1) cerr << "hier4: " << ans << endl;
        printf("%lld\n", ans);
    }
    return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'void single_update(int, long long int)':
foehn_phenomena.cpp:12:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=start; i<ft.size(); i+=i&(-i))
                      ~^~~~~~~~~~
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %lld %lld", &n, &q, &s, &t);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:48:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0; i<n; i++) scanf("%lld", &heights[i]);
                            ~~~~~^~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %lld", &from, &to, &by);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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