Submission #205548

#	Time	Username	Problem	Language	Result	Execution time	Memory
205548		Kastanda	Foehn Phenomena (JOI17_foehn_phenomena)	C++11	100 / 100	374 ms	20736 KiB

foehn_phenomena

// In The Name Of The Queen
#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (lc ^ 1)
#define md (l + r >> 1)
using namespace std;
typedef long long ll;
const int N = 200005;
int n, q, S, T, A[N];
ll F[N], C[N * 4][2];
inline void Add(int i, int val)
{
    for (i ++; i < N; i += i & - i)
        F[i] += val;
}
inline ll Get(int i)
{
    ll rt = 0;
    for (i ++; i; i -= i & - i)
        rt += F[i];
    return (rt);
}
void Set(int i, ll a, ll b, int id = 1, int l = 0, int r = n)
{
    if (r - l < 2)
    {
        C[id][0] = C[id][1] = 0;
        C[id][a < b] += abs(a - b);
        return ;
    }
    if (i < md)
        Set(i, a, b, lc, l, md);
    else
        Set(i, a, b, rc, md, r);
    C[id][0] = C[lc][0] + C[rc][0];
    C[id][1] = C[lc][1] + C[rc][1];
}
int main()
{
    scanf("%d%d%d%d", &n, &q, &S, &T);
    for (int i = 0; i <= n; i ++)
        scanf("%d", &A[i]), Add(i, A[i]), Add(i + 1, -A[i]);
    for (int i = 0; i < n; i ++)
        Set(i, A[i], A[i + 1]);
    for (int i = 1; i <= q; i ++)
    {
        int l, r, X;
        scanf("%d%d%d", &l, &r, &X);
        Add(l, X); Add(r + 1, -X);
        Set(l - 1, Get(l - 1), Get(l));
        if (r < n)
            Set(r, Get(r), Get(r + 1));
        printf("%lld\n", C[1][0] * T - C[1][1] * S);
    }
    return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'void Set(int, ll, ll, int, int, int)':
foehn_phenomena.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
foehn_phenomena.cpp:31:13: note: in expansion of macro 'md'
     if (i < md)
             ^~
foehn_phenomena.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
foehn_phenomena.cpp:32:29: note: in expansion of macro 'md'
         Set(i, a, b, lc, l, md);
                             ^~
foehn_phenomena.cpp:5:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define md (l + r >> 1)
             ~~^~~
foehn_phenomena.cpp:34:26: note: in expansion of macro 'md'
         Set(i, a, b, rc, md, r);
                          ^~
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &q, &S, &T);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:42:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]), Add(i, A[i]), Add(i + 1, -A[i]);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
foehn_phenomena.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &l, &r, &X);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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