Submission #144950

#	Time	Username	Problem	Language	Result	Execution time	Memory
144950		blue	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	0 / 100	1056 ms	22472 KiB

foehn_phenomena

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

int N;
int* A;

map<int, int> M;

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

void build(int p1, int 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;
    }
}

int E(int p1, int p2, int 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);
}

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

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

int main()
{
    int Q, S, T;
    cin >> N >> Q >> S >> T;
    
    A = new int[N+1];
    for(int i = 0; i <= N; i++) cin >> A[i];
    
    build(1, N);
    
    int w = 0;
    for(int i = 1; i <= N; i++) w += (A[i-1]-A[i]) * ((A[i]>A[i-1])?S:T);
    int l, r, u;
    int L1, L2, R1, R2;
    for(int 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: 0 / 30
• Subtask 2: 0 / 10
• Subtask 3: 0 / 60