Submission #116644

#	Time	Username	Problem	Language	Result	Execution time	Memory
116644		roseanne_pcy	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	100 / 100	203 ms	13048 KiB

foehn_phenomena

//I don't want a lot for Christmas
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vvi vector< vi >
#define vii vector< ii >
#define mp make_pair
#define pb push_back
const int maxn = 2e5+5;
ll ft[maxn];
int n;
ll a[maxn];
void update(int x, int dx)
{
    for(; x<= n; x+=x&(-x)) ft[x] += dx;
}
ll sum(int x)
{
    ll res = 0;
    for(; x; x -= x&(-x)) res += ft[x];
    return res;
}
ll ask(int a, int b)
{
    return sum(a);
}
void add(int a, int b, int dx)
{
    update(a, dx);
    update(b+1, -dx);
}
int main()
{
    //#ifndef atom freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif
    int q, s, t; scanf("%d %d %d %d", &n, &q, &s, &t);
    for(int i = 0; i<= n; i++) scanf("%lld", a+i);
    ll now = 0;
    for(int i = 0; i+1<= n; i++)
    {
        int dx = abs(a[i]-a[i+1]);
        if(a[i]< a[i+1])
        {
            now -= 1LL*s*dx;
        }
        else now += 1LL*t*dx;
    }
    for(int i = 1; i<= n; i++)
    {
        add(i, i, (int)a[i]);
    }
    while(q--)
    {
        //printf("%d\n", q);
        int L, R, x; scanf("%d %d %d", &L, &R, &x);
        ll aL = ask(L-1, L-1);
        ll aLp = ask(L, L);
        //printf("*%d %d\n", aL, aLp);
        ll dx = abs(aL-aLp);
        if(aL< aLp) now += 1LL*s*dx;
        else now -= 1LL*t*dx;
        aLp += x;
        dx = abs(aL-aLp);
        if(aL< aLp) now -= 1LL*s*dx;
        else now += 1LL*t*dx;
        //printf("temp %lld\n", now);
        if(R == n)
        {
            add(L, R, x);
            printf("%lld\n", now);
            continue;
        }
        aL = ask(R, R);
        aLp = ask(R+1, R+1);
        //printf("**%d %d\n", aL, aLp);
        dx = abs(aL-aLp);
        if(aL< aLp) now += 1LL*s*dx;
        else now -= 1LL*t*dx;
        aL += x;
        dx = abs(aL-aLp);
        if(aL< aLp) now -= 1LL*s*dx;
        else now += 1LL*t*dx;
        add(L, R, x);
        printf("%lld\n", now);
    }
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:40:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int q, s, t; scanf("%d %d %d %d", &n, &q, &s, &t);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:41:37: 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", a+i);
                                ~~~~~^~~~~~~~~~~~~
foehn_phenomena.cpp:59:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int L, R, x; scanf("%d %d %d", &L, &R, &x);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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