제출 #332024

#제출 시각아이디문제언어결과실행 시간메모리
332024Atill83Foehn Phenomena (JOI17_foehn_phenomena)C++14
100 / 100
422 ms26860 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define endl '\n' using namespace std; const long long INF = (long long) 1e18; const int mod = (int) 1e9+7; const int MAXN = (int) 3e5+5; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll n, q, s, T; ll a[MAXN]; struct node{ ll lazy, val, left, right; } t[4*MAXN]; void build(int v, int tl, int tr){ if(tl == tr) t[v] = {0, 0, a[tl], a[tl]}; else{ int tm = (tl + tr) / 2; build(2*v, tl, tm); build(2*v+1, tm + 1, tr); t[v].left = t[2*v].left; t[v].right = t[2*v + 1].right; t[v].lazy = 0; t[v].val = t[2*v].val + (t[2*v].right >= t[2*v + 1].left ? T : -s)*abs(t[2*v].right - t[2*v + 1].left) + t[2*v + 1].val; } } void push(int v){ ll lz = t[v].lazy; t[v].lazy = 0; if(!lz) return; t[2*v].left += lz; t[2*v + 1].left += lz; t[2*v].right += lz; t[2*v + 1].right += lz; t[2*v].lazy += lz; t[2*v + 1].lazy += lz; } void upd(int v, int tl, int tr, int l, int r, ll val){ if(l > r) return; if(tl == l && tr == r){ t[v].left += val; t[v].right += val; t[v].lazy += val; }else{ push(v); int tm = (tl + tr) / 2; upd(2*v, tl, tm, l, min(tm, r), val); upd(2*v + 1, tm + 1, tr, max(tm + 1, l), r, val); t[v].left = t[2*v].left; t[v].right = t[2*v + 1].right; t[v].lazy = 0; t[v].val = t[2*v].val + (t[2*v].right >= t[2*v + 1].left ? T : -s)*abs(t[2*v].right - t[2*v + 1].left) + t[2*v + 1].val; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); #ifdef Local freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin); freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout); #endif cin>>n>>q>>s>>T; for(int i = 0; i <= n; i++) cin>>a[i]; build(1, 0, n); while(q--){ int l, r, x; cin>>l>>r>>x; upd(1, 0, n, l, r, x); cout<<t[1].val<<endl; } #ifdef Local cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...