Submission #144953

#	Time	Username	Problem	Language	Result	Execution time	Memory
144953		blue	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	30 / 100	1084 ms	27464 KiB

foehn_phenomena

#include <iostream>
#include <map>
using namespace std;

long long N;
long long* A;

map<long long, long long> M;

long long g(long long p1, long long p2)
{
    return (N+1)*p1 + p2;
}

void build(long long p1, long long p2)
{
    if(p1 == p2) M[g(p1, p2)] = A[p1];
    else
    {
        build(p1, (p1+p2)/2);
        build((p1+p2)/2 + 1, p2);
        M[g(p1, p2)] = 0;
    }
}

long long E(long long p1, long long p2, long long p)
{
    if(p1 == p2) return M[g(p1, p2)];
    if(p <= (p1+p2)/2) return M[g(p1, p2)] + E(p1, (p1+p2)/2, p);
    else return M[g(p1, p2)] + E((p1+p2)/2 + 1, p2, p);
}

long long F(long long p)
{
    if(p == 0) return 0;
    return E(1, N, p);
}

void update(long long p1, long long p2, long long a1, long long a2, long long u) //map range, update range, update value
{
    if(a2 < p1 || p2 < a1) return;
    if(a1 <= p1 && p2 <= a2)
    {
        M[g(p1, p2)] += u;
        return;
    }
    if(a1 <= (p1+p2)/2) update(p1, (p1+p2)/2, a1, a2, u);
    if(a2 > (p1+p2)/2) update((p1+p2)/2 + 1, p2, a1, a2, u);
}

int main()
{
    long long Q, S, T;
    cin >> N >> Q >> S >> T;
    
    A = new long long[N+1];
    for(long long i = 0; i <= N; i++) cin >> A[i];
    
    build(1, N);
    
    long long w = 0;
    for(long long i = 1; i <= N; i++) w += (A[i-1]-A[i]) * ((A[i]>A[i-1])?S:T);
    long long l, r, u;
    long long L1, L2, R1, R2;
    for(long long i = 1; i <= Q; i++)
    {
        cin >> l >> r >> u;
        L1 = F(l-1);
        L2 = F(l);
        if(r != N) 
        {
            R1 = F(r); 
            R2 = F(r+1);
        }
        w -= (L1-L2) * ((L2>L1)?S:T);
        if(r != N) w -= (R1-R2) * ((R2>R1)?S:T);
        update(1, N, l, r, u);
        
        L1 = F(l-1);
        L2 = F(l);
        if(r != N) 
        {
            R1 = F(r); 
            R2 = F(r+1);
        }
        
        w += (L1-L2) * ((L2>L1)?S:T);
        if(r != N) w += (R1-R2) * ((R2>R1)?S:T);
        cout << w << '\n';
    }
    return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:76:28: warning: 'R2' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(r != N) w -= (R1-R2) * ((R2>R1)?S:T);
                         ~~~^~~~
foehn_phenomena.cpp:76:28: warning: 'R1' may be used uninitialized in this function [-Wmaybe-uninitialized]

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