Submission #391019

#	Time	Username	Problem	Language	Result	Execution time	Memory
391019		cpp219	Foehn Phenomena (JOI17_foehn_phenomena)	C++14	0 / 100	1094 ms	25432 KiB

foehn_phenomena

#pragma GCC optimization "Ofast"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e5 + 9;
const ll inf = 1e18 + 7;
const ll Log2 = 20;
typedef pair<ll,ll> LL;

ll n,Q,s,t,a[N],temp[N];
ll st[2][4*N],lazy[2][4*N],L,R,x;

void Pass(ll cond,ll id){
    ll t = lazy[cond][id]; lazy[cond][id] = 0;
    st[cond][id*2] += t; st[cond][id*2 + 1] += t;
    lazy[cond][id*2] += t; lazy[cond][id*2 + 1] += t;
}

void upd(ll cond,ll id,ll l,ll r,ll u,ll v,ll val){
    if (v < l||r < u) return;
    if (u <= l&&r <= v){
        st[cond][id] += val; lazy[cond][id] += val;
        return;
    }
    ll mid = (l + r)/2; Pass(cond,id);
    upd(cond,id*2,l,mid,u,v,val); upd(cond,id*2 + 1,mid + 1,r,u,v,val);
    st[cond][id] = max(st[cond][id*2],st[cond][id*2 + 1]);
}

ll Get(ll cond,ll id,ll l,ll r,ll u){
    if (!u) return 0;
    if (u < l||r < u) return -inf;
    if (l == r) return st[cond][id];
    ll mid = (l + r)/2; Pass(cond,id);
    return max(Get(cond,id*2,l,mid,u),Get(cond,id*2 + 1,mid + 1,r,u));
}
/// 0 for a     1 for temp

ll Get_temp(ll a,ll b){
    if (a < b) return (a - b)*s;
    return (a - b)*t;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n>>Q>>s>>t;
    for (ll i = 0;i <= n;i++) cin>>a[i];
    for (ll i = 0;i < n;i++){
        temp[i + 1] = temp[i];
        if (a[i] < a[i + 1]) temp[i + 1] -= (a[i + 1] - a[i])*s;
        else temp[i + 1] += (a[i] - a[i + 1])*t;
        upd(0,1,1,n,i + 1,i + 1,a[i + 1]); upd(1,1,1,n,i + 1,i + 1,temp[i + 1]);
    }
    //cout<<temp[1]; return 0;
    //for (ll i = 1;i <= n;i++) cout<<Get(1,1,1,n,i)<<" "; return 0;
    while(Q--){
        cin>>L>>R>>x;
        ll prv0 = Get(0,1,1,n,L),prv1 = Get(1,1,1,n,L);
        ll new_temp = prv0 + x; new_temp = Get(1,1,1,n,L - 1) + Get_temp(Get(0,1,1,n,L - 1),new_temp);
        ll diff = new_temp - prv1; //cout<<diff; return 0;
        upd(1,1,1,n,L,R,diff); upd(0,1,1,n,L,R,x);
        ll diff2 = Get(1,1,1,n,R) + Get_temp(Get(0,1,1,n,R),Get(0,1,1,n,R + 1)) - Get(1,1,1,n,R + 1);
        //cout<<diff2; exit(0);
        //upd(1,1,1,n,R + 1,n,diff2);
        //for (ll i = 1;i <= n;i++) cout<<Get(1,1,1,n,i)<<" "; return 0;
        cout<<Get(1,1,1,n,n)<<"\n";
    }
}

Compilation message (stderr)

foehn_phenomena.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    1 | #pragma GCC optimization "Ofast"
      | 
foehn_phenomena.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
foehn_phenomena.cpp: In function 'int main()':
foehn_phenomena.cpp:74:12: warning: unused variable 'diff2' [-Wunused-variable]
   74 |         ll diff2 = Get(1,1,1,n,R) + Get_temp(Get(0,1,1,n,R),Get(0,1,1,n,R + 1)) - Get(1,1,1,n,R + 1);
      |            ^~~~~
foehn_phenomena.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   55 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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