Submission #155174

#	Time	Username	Problem	Language	Result	Execution time	Memory
155174		mat_v	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	30 / 100	1061 ms	11760 KiB

foehn_phenomena

#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define mod 1000000007
#define pb push_back
#define mid(l, r) ((l)+(r))/2
#define len(a) (a).length()
#define sz(a) (a).size()
#define xx first
#define yy second
#define inf int(2e9)
#define ff(i, a, b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i, a, b) for(int (i) = (a); (i) >= (b); --(i))
#define maxn 200005

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

template<class T>
void print(const T niz[], const int siz)
{
    for(int i=0;i<siz;i++)
        cout << niz[i] << " ";
    cout << endl;
}

int n,q;
ll s,t;
ll niz[4*maxn];
ll seg[8*maxn];
ll lazy[8*maxn];
ll go,dl;
void init(int node, int l, int r){
    if(l == r){
        seg[node] = niz[l];
        return;
    }
    int mid = (l + r) >> 1;
    init(node*2,l,mid);
    init(node*2+1,mid+1,r);
    seg[node] = seg[node * 2] + seg[node * 2 + 1];
}
void propage(int node, int l, int r){
    seg[node] += (r - l + 1) * lazy[node];
    if(l < r){
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
}
void update(int node, int l, int r, int levo, int desno, ll val){
    propage(node, l, r);
    if(r < levo || l > desno)return;
    if(l >= levo && r <= desno){
        lazy[node] += val;
        propage(node, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    update(node*2,l,mid,levo,desno,val);
    update(node*2+1,mid+1,r,levo,desno,val);
    propage(node*2,l,mid);
    propage(node*2+1,mid+1,r);
    seg[node] = seg[node * 2] + seg[node * 2 + 1];
}
ll query(int node, int l, int r, int poz){
    propage(node,l,r);
    if(l == r)return seg[node];
    int mid = (l + r) >> 1;
    if(poz <= mid)return query(node*2,l,mid,poz);
    else return query(node*2+1,mid+1,r,poz);
}
ll get(int x){
    if(x == 0)return 0;
    return query(1,1,n,x);
    if(x>n)return 0;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cerr.tie(NULL);
    cout.tie(NULL);
    cin >> n >> q >> s >> t;
    ff(i,0,n)cin >> niz[i];
    ff(i,0,n - 1){
        if(niz[i] < niz[i + 1])go += (niz[i+1] - niz[i]);
        else dl += (niz[i] - niz[i + 1]);
    }
    init(1,1,n);
    while(q--){
        int l,r;
        ll x;
        cin >> l >> r >> x;
        ll a,b,c,d=1e9;
        a = get(l-1);
        b = get(l);
        c = get(r);
        if(r != n)d = get(r+1);
        if(a < b)go -= (b-a);
        else dl -= (a-b);
        b += x;
        if(a < b)go += (b-a);
        else dl += (a-b);
        if(r != n){
            if(c < d)go -= (d-c);
            else dl -= (c-d);
            c += x;
            if(c < d)go += (d-c);
            else dl += (c-d);
        }
        cout << dl*t - s*go << endl;
        update(1,1,n,l,r,x);
    }
    return 0;
}

Compilation message (stderr)

foehn_phenomena.cpp:2:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")

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